Alice and Bob are playing a game. Initially, Alice has a string word = "a".
You are given a positive integer k. You are also given an integer array operations, where operations[i] represents the type of the ith operation.
Now Bob will ask Alice to perform all operations in sequence:
operations[i] == 0, append a copy of word to itself.operations[i] == 1, generate a new string by changing each character in word to its next character in the English alphabet, and append it to the original word. For example, performing the operation on "c" generates "cd" and performing the operation on "zb" generates "zbac".Return the value of the kth character in word after performing all the operations.
Note that the character 'z' can be changed to 'a' in the second type of operation.
Example 1:
Input: k = 5, operations = [0,0,0]
Output: "a"
Explanation:
Initially, word == "a". Alice performs the three operations as follows:
"a" to "a", word becomes "aa"."aa" to "aa", word becomes "aaaa"."aaaa" to "aaaa", word becomes "aaaaaaaa".Example 2:
Input: k = 10, operations = [0,1,0,1]
Output: "b"
Explanation:
Initially, word == "a". Alice performs the four operations as follows:
"a" to "a", word becomes "aa"."bb" to "aa", word becomes "aabb"."aabb" to "aabb", word becomes "aabbaabb"."bbccbbcc" to "aabbaabb", word becomes "aabbaabbbbccbbcc".
Constraints:
1 <= k <= 10141 <= operations.length <= 100operations[i] is either 0 or 1.word has at least k characters after all operations.Problem Overview: You start with a base string and repeatedly apply operations that transform and expand it. The length grows exponentially, so constructing the full string quickly becomes impossible. The task is to determine the k-th character in the final string without actually building the entire sequence.
Approach 1: Simulate Operations with Direct Calculation (O(n) time, O(1) space)
This method analyzes how each operation affects character shifts instead of physically generating the string. Each step effectively doubles the length and may apply a transformation (such as shifting characters forward in the alphabet). You track whether the index k falls in the original half or the transformed half after each expansion. If it falls in the second half, reduce the index to the corresponding position in the first half and accumulate the transformation count. The final character can then be computed using modular arithmetic on the alphabet. This approach relies heavily on math and bit manipulation to track how many transformations affect the target position.
Approach 2: Recursive Length Calculation with Reduction (O(log k) time, O(log k) space)
This approach treats the process as a recursive structure where each step creates a string composed of two halves: the previous string and its transformed version. Instead of simulating forward, compute the total length growth and recursively determine which half contains the target index. If k lies in the first half, recurse directly on that range. If it lies in the second half, subtract the half length, recurse on the mirrored index, and apply the required character shift. Because the string length doubles each step, the recursion depth is logarithmic relative to k. The logic maps cleanly to divide-and-conquer using recursion.
Recommended for interviews: The recursive reduction approach is usually preferred. It demonstrates that you recognize the exponential growth pattern and avoid explicit simulation. Explaining the direct calculation method first can show understanding of the transformation mechanics, but the logarithmic recursive solution highlights stronger algorithmic thinking and scalability awareness.
This approach involves simulating the operations but focuses on efficiently calculating the length of the string after each operation, instead of building the entire string. This is feasible due to the rapidly increasing length after each operation.
As we iterate through the operations, keep track of the length of the string after each operation is performed. Instead of growing the string, calculate what the length would be, tracking this incrementally.
Once the total length is known, locate where the k-th character is within the operations' results using the calculated lengths.
This Python solution efficiently calculates the length of the string after each operation, without constructing the string. By maintaining the growing length, it determines the segment in which the k-th character resides, and then backtracks through the operations to locate and identify the character.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n) where n is the number of operations because we iterate over the operations twice.
Space Complexity: O(1) since storing a few integer variables only.
Rather than directly growing or calculating the full length, consider a recursive approach to track what operation modifies length.
By recursively reducing the operations and finding length, the k-th index can be tracked back through recursive reductions.
The approach considers whether each operation, when halved recursively, results in a k that is larger or smaller than the halved length and adjusts recursively.
A recursive Python solution utilizing recursion to continuously reduce operations and determine where the kth falls in reduced-size operations. This avoids generating the string by finding length recursively.
Python
C++
Java
C#
JavaScript
Time Complexity: O(n), similar to iterative solution due to recursion depth.
Space Complexity: O(n) for recursion depth.
Since the length of the string doubles after each operation, if we perform i operations, the length of the string will be 2^i.
We can simulate this process to find the first string length n that is greater than or equal to k.
Next, we backtrack and discuss the following cases:
k \gt n / 2, it means k is in the second half. If operations[i - 1] = 1, it means the character at position k is obtained by adding 1 to the character in the first half. We add 1 to it. Then we update k to k - n / 2.k \le n / 2, it means k is in the first half and is not affected by operations[i - 1].n to n / 2 and continue backtracking until n = 1.Finally, we take the resulting number modulo 26 and add the ASCII code of 'a' to get the answer.
The time complexity is O(log k), and the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Simulate Operations with Direct Calculation | Time Complexity: O(n) where n is the number of operations because we iterate over the operations twice. |
| Approach 2: Recursive Length Calculation with Reduction | Time Complexity: O(n), similar to iterative solution due to recursion depth. |
| Recurrence | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simulate Operations with Direct Calculation | O(n) | O(1) | When the number of operations is small and you want a straightforward iterative reasoning of how transformations affect the index. |
| Recursive Length Calculation with Reduction | O(log k) | O(log k) | Best general solution when the string length grows exponentially and constructing the string is infeasible. |
Find the K-th Character in String Game II | Recursion | Dry Run | Leetcode 3307 | codestorywithMIK • codestorywithMIK • 13,259 views views
Watch 9 more video solutions →Practice Find the K-th Character in String Game II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor