Watch 10 video solutions for Find the K-th Character in String Game II, a hard level problem involving Math, Bit Manipulation, Recursion. This walkthrough by codestorywithMIK has 13,259 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |