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.

Description Hints 2 Solution Video 31:22

3307. Find the K-th Character in String Game II

Hard48.5% acceptance3 companies

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 i^th 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 k^th 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 <= 10¹⁴
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.

Asked at 3 companies

Google Amazon Bloomberg

Topics

Hints open one at a time

Hint 1

Try to replay the operations k^th character was part of.

Hint 2

The k^th character is only affected if it is present in the first half of the string.

31:22

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution