Skip to main content
Talentd

Find the K-th Character in String Game II - Solution & Explanation

HardMathBit ManipulationRecursion21 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

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:

  • If operations[i] == 0, append a copy of word to itself.
  • If 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:

  • Appends "a" to "a", word becomes "aa".
  • Appends "aa" to "aa", word becomes "aaaa".
  • Appends "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:

  • Appends "a" to "a", word becomes "aa".
  • Appends "bb" to "aa", word becomes "aabb".
  • Appends "aabb" to "aabb", word becomes "aabbaabb".
  • Appends "bbccbbcc" to "aabbaabb", word becomes "aabbaabbbbccbbcc".

 

Constraints:

  • 1 <= k <= 1014
  • 1 <= operations.length <= 100
  • operations[i] is either 0 or 1.
  • The input is generated such that word has at least k characters after all operations.

Approach Overview

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 1: Approach 1: Simulate Operations with Direct Calculation

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Recursive Length Calculation with Reduction

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.

Code

PythonC++JavaC#JavaScript

Python

C++

Java

C#

JavaScript

Complexity

Time Complexity: O(n), similar to iterative solution due to recursion depth.
Space Complexity: O(n) for recursion depth.

Try this approach in the editor →

Approach 3: Recurrence

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:

  • If 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.
  • If k \le n / 2, it means k is in the first half and is not affected by operations[i - 1].
  • Next, we update 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).

Code

PythonJavaC++GoTypeScriptRustC#PHP

Python

Java

C++

Go

TypeScript

Rust

C#

PHP

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(1) since storing a few integer variables only.

Approach 2: Recursive Length Calculation with Reduction

Time Complexity: O(n), similar to iterative solution due to recursion depth.
Space Complexity: O(n) for recursion depth.

Recurrence—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Simulate Operations with Direct CalculationO(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 ReductionO(log k)O(log k)Best general solution when the string length grows exponentially and constructing the string is infeasible.

Video Solution

Find the K-th Character in String Game II | Recursion | Dry Run | Leetcode 3307 | codestorywithMIK • codestorywithMIK • 13,799 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Find the K-th Character in String Game II easy or hard?
Find the K-th Character in String Game II is classified as a Hard problem. The challenge comes from recognizing that the string grows exponentially and that the correct solution requires mathematical reasoning, recursion, and bit-level index reduction rather than direct simulation.
Find the K-th Character in String Game II Python/Java solution
Python, Java, C++, C#, and JavaScript solutions typically implement the recursive reduction or iterative index tracking approach. Each version calculates whether k lies in the original or transformed half, reduces the index accordingly, and applies character shifts using modular arithmetic.
How to solve Find the K-th Character in String Game II in O(log k)?
Compute how the string length grows after each operation and treat the structure as two halves: the original string and its transformed copy. If k falls in the second half, subtract the half length and record the transformation. Repeat until reaching the base character, then apply the accumulated shifts.
What is the best approach for Find the K-th Character in String Game II?
The most efficient approach uses recursive length reduction. Instead of constructing the exponentially growing string, you determine whether the k-th index lies in the original half or the transformed half of each expansion. By repeatedly reducing the index and tracking character shifts, the problem can be solved in O(log k) time.
Is Find the K-th Character in String Game II asked at Google/Amazon/Meta?
Problems involving recursive string construction, index reduction, and transformation tracking frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test whether candidates can avoid building exponential strings and instead compute positions mathematically.
What data structure is used in Find the K-th Character in String Game II?
The problem primarily relies on mathematical reasoning and recursion rather than complex data structures. Bit manipulation and index arithmetic are used to determine which half of the constructed string contains the k-th character.
What is the time complexity of Find the K-th Character in String Game II?
The optimal solution runs in O(log k) time because each step reduces the search space by half as the string doubles in size after every operation. Space complexity is O(log k) when implemented recursively due to the recursion stack.

Ready to solve this problem?

Practice Find the K-th Character in String Game II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Shifting Letters