Find the K-th Character in String Game I

Find the K-th Character in String Game I

What is this problem about?

The Find the K-th Character in String Game I interview question is a simulation based on string expansion rules. You start with the string "a". In each step, you generate a new string by taking the current string, incrementing each character (e.g., 'a' -> 'b', 'z' -> 'a'), and appending it to the end. You need to find the $k^{th}$ character after several operations.

Why is this asked in interviews?

Companies like Meta and Microsoft ask this to test basic Simulation and string handling. It evaluations if you can identify that for small $k$, you can simply perform the operations until the string length exceeds $k$. It also serves as a baseline for the harder version where $k$ is much larger.

Algorithmic pattern used

This follows the Iterative Simulation pattern.

1. Initialize: s = "a".
2. Loop: While s.length < k:

• Create a temporary string nextPart.
• For each char in s, increment it and add to nextPart.
• s = s + nextPart.

1. Return: s[k - 1].

Example explanation

$k = 5$

1. Start: "a"
2. Step 1: "a" + "b" = "ab"
3. Step 2: "ab" + "bc" = "abbc"
4. Step 3: "abbc" + "bccd" = "abbcbccd"
5. The $5^{th}$ character is 'b'.

Common mistakes candidates make

• Off-by-one: Confusion between 1-based index $k$ and 0-based array index.
• Inefficient Appending: Using immutable string concatenation in a loop (like s += nextPart in Java or Python), which can be $O(N^2)$. Use a StringBuilder or list of characters.

Interview preparation tip

Always look for the growth rate. In this game, the string length doubles in every step. This means you only need $\log_2(k)$ steps to reach any $k$. This logarithmic growth is a hint that recursion or bitwise logic might also apply.