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:
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 <= 105s contains only lowercase English letters and spaces ' '.s does not contain any leading or trailing spaces.s are separated by a single space.0 <= k < t.length. That is, k is a valid index of t.Problem Overview: You are given a compressed or encoded string where expansion rules create a much longer final string. The task is to return the kth character of the fully expanded result without explicitly building the entire string.
Approach 1: Full Expansion Simulation (O(n * m) time, O(n * m) space)
The most straightforward method is to simulate the expansion directly. Iterate through the input string, append characters, and repeat segments when digits indicate expansion. After constructing the full string, return the character at index k - 1. This approach is simple to reason about but quickly becomes impractical when the expanded string grows to millions or billions of characters. It also consumes significant memory since the entire expanded result must be stored.
Approach 2: Math + Length Simulation (O(n) time, O(1) space)
The efficient strategy avoids building the expanded string. Instead, track the length of the string that would result from expansion. Iterate through the encoded string and update a running length: letters increase the length by one, while digits multiply the current length because they repeat the existing sequence. Once the simulated length reaches or exceeds k, traverse the string backward. Reduce k using modulo operations when encountering repetition and decrease the length when stepping past characters. When k matches a character position, you’ve found the answer.
This works because repetition does not change character order—only how many times a prefix appears. Tracking length mathematically lets you map the kth position in the expanded string back to a position in the original encoded sequence.
Problems like this are common in string processing where expansion rules produce massive outputs. The trick is recognizing that the output size can exceed memory limits, which pushes you toward a math-based reasoning approach combined with careful simulation of lengths rather than characters.
Recommended for interviews: The Math + Simulation approach. Interviewers expect you to recognize that full expansion is infeasible for large inputs. Demonstrating the brute force idea shows baseline understanding, but deriving the length-tracking method shows strong problem-solving and complexity awareness.
We first split the string s into multiple words by spaces. For each word w, we can calculate the length it occupies in the expanded string t as m=\frac{(1+|w|)cdot |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:
cur = 0 to represent the number of characters that have been expanded so far.w[i] of the word w:cur by i + 1.k < cur, it means the k-th character is 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 s.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Full Expansion Simulation | O(n * m) | O(n * m) | Small inputs where expanded size remains manageable |
| Math + Length Simulation | O(n) | O(1) | Large expansions where building the full string is impossible |
Practice Find Kth Character in Expanded String with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor