Find Kth Character in Expanded String - Video Solutions
Find Kth Character in Expanded String
Find Kth Character in Expanded String - Video Solution
Watch the video solution for Find Kth Character in Expanded String, a medium level problem involving String. This walkthrough by Owen Wu has 2 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 105scontains only lowercase English letters and spaces' '.sdoes not contain any leading or trailing spaces.- All the words in
sare separated by a single space. 0 <= k < t.length. That is,kis a valid index oft.
Approach Overview
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.
Complexity Analysis
| 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 |