Find the K-th Character in String Game II

Find the K-th Character in String Game II

What is this problem about?

The Find the K-th Character in String Game II interview question is the "Hard" version of the expansion game. You are given a sequence of operations (type 0: copy, type 1: increment then copy). Because $k$ can be as large as $10^{15}$, you cannot actually build the string. You must find the $k^{th}$ character using the properties of the operations.

Why is this asked in interviews?

Amazon and Google ask this to evaluate a candidate's ability to use Recursion and Bit Manipulation. It requires the insight that the character at index $k$ is determined by how many "Type 1" operations were applied to that specific bit position during the doubling process.

Algorithmic pattern used

This problem is solved using Recursive Backtracking or Bitwise Parity.

1. Reverse Mapping: To find the character at index $k$, look at its origin in the previous step.

• If $k$ is in the first half, the operation doesn't affect it.
• If $k$ is in the second half, it was generated from index k - (half_length).

1. Bit Interpretation: If the operation that generated the second half was "Type 1," increment a "shift" counter.
2. Base Case: When you reach the initial character "a" (index 0), the final character is 'a' plus the total "shift" count modulo 26.

Example explanation

$k = 5$, operations: [0, 1, 1]

1. $k=5$ is in second half of step 3 (length 8). Origin is $5 - 4 = 1$. Op 3 is Type 1. shift = 1.
2. $k=1$ is in second half of step 2 (length 4). Origin is $1 - 2$? No, step 2 has length 2. Wait, origin is $1 - 2$ is negative.
3. Correct logic: $k=5$ comes from $k=1$ in step 2. $k=1$ comes from $k=1$ in step 1. $k=1$ in step 1 (len 2) comes from $k=0$.
4. Sum the "Type 1" operations used to reach $k=0$.

Common mistakes candidates make

• Memory errors: Attempting to build even a part of the string.
• Calculation errors: Miscalculating the power of 2 boundaries.
• Integer Overflow: Forgetting that $k$ and lengths exceed 32-bit limits.

Interview preparation tip

When $k$ is very large, the problem is almost always about Bitwise Decomposition or logarithmic recursion. Think about how $k$ is represented in binary and how each bit corresponds to an operation.