Welcome to Subscribe On Youtube

3744. Find Kth Character in Expanded String 🔒

Description

You are given a string s consisting of one or more words separated by single spaces. Each word in s consists of lowercase English letters.

We obtain the expanded string t from s as follows:

• For each word in s, repeat its first character once, then its second character twice, and so on.

For example, if s = "hello world", then t = "heelllllllooooo woorrrllllddddd".

You are also given an integer k, representing a valid index of the string t.

Return the kth character of the string t.

 

Example 1:

Input: s = "hello world", k = 0

Output: "h"

Explanation:

t = "heelllllllooooo woorrrllllddddd". Therefore, the answer is t[0] = "h".

Example 2:

Input: s = "hello world", k = 15

Output: " "

Explanation:

t = "heelllllllooooo woorrrllllddddd". Therefore, the answer is t[15] = " ".

 

Constraints:

• 1 <= s.length <= 105
• s contains only lowercase English letters and spaces ' '.
• s does not contain any leading or trailing spaces.
• All the words in s are separated by a single space.
• 0 <= k < t.length. That is, k is a valid index of t.

Solutions

Solution 1: Math + Simulation

We first split the string $\textit{s}$ into multiple words by spaces. For each word $\textit{w}$, we can calculate the length it occupies in the expanded string $\textit{t}$ as $m=\frac{(1+|\textit{w}|)\cdot |\textit{w}|}{2}$.

If $k = m$, it means the $k$-th character is a space, and we can directly return a space.

If $k > m$, it means the $k$-th character is not in the expanded part of the current word. We subtract the expanded length $m$ of the current word and the space length $1$ from $k$, and continue processing the next word.

Otherwise, the $k$-th character is in the expanded part of the current word. We can find the $k$-th character by simulating the expansion process:

• Initialize a variable $\textit{cur} = 0$ to represent the number of characters that have been expanded so far.
• Iterate through each character $\textit{w}[i]$ of the word $\textit{w}$:
  • Increase $\textit{cur}$ by $i + 1$.
  • If $k < \textit{cur}$, it means the $k$-th character is $\textit{w}[i]$, and we return this character.

The time complexity is $O(n)$ and the space complexity is $O(n)$, where $n$ is the length of the string $\textit{s}$.

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public char kthCharacter(String s, long k) {
          for (String w : s.split(" ")) {
              long m = (1L + w.length()) * w.length() / 2;
              if (k == m) {
                  return ' ';
              }
              if (k > m) {
                  k -= m + 1;
              } else {
                  long cur = 0;
                  for (int i = 0;; ++i) {
                      cur += i + 1;
                      if (k < cur) {
                          return w.charAt(i);
                      }
                  }
              }
          }
          return ' ';
      }
  }
  
  

• class Solution {
  public:
      char kthCharacter(string s, long long k) {
          stringstream ss(s);
          string w;
          while (ss >> w) {
              long long m = (1 + (long long) w.size()) * (long long) w.size() / 2;
              if (k == m) {
                  return ' ';
              }
              if (k > m) {
                  k -= m + 1;
              } else {
                  long long cur = 0;
                  for (int i = 0;; ++i) {
                      cur += i + 1;
                      if (k < cur) {
                          return w[i];
                      }
                  }
              }
          }
          return ' ';
      }
  };
  
  

• class Solution:
      def kthCharacter(self, s: str, k: int) -> str:
          for w in s.split():
              m = (1 + len(w)) * len(w) // 2
              if k == m:
                  return " "
              if k > m:
                  k -= m + 1
              else:
                  cur = 0
                  for i in range(len(w)):
                      cur += i + 1
                      if k < cur:
                          return w[i]
  
  

• func kthCharacter(s string, k int64) byte {
  	for _, w := range strings.Split(s, " ") {
  		m := (1 + int64(len(w))) * int64(len(w)) / 2
  		if k == m {
  			return ' '
  		}
  		if k > m {
  			k -= m + 1
  		} else {
  			var cur int64
  			for i := 0; ; i++ {
  				cur += int64(i + 1)
  				if k < cur {
  					return w[i]
  				}
  			}
  		}
  	}
  	return ' '
  }
  
  

• function kthCharacter(s: string, k: number): string {
      for (const w of s.split(' ')) {
          const m = ((1 + w.length) * w.length) / 2;
          if (k === m) {
              return ' ';
          }
          if (k > m) {
              k -= m + 1;
          } else {
              let cur = 0;
              for (let i = 0; ; ++i) {
                  cur += i + 1;
                  if (k < cur) {
                      return w[i];
                  }
              }
          }
      }
      return ' ';
  }
  
  

All Problems

All Solutions