Purav Patel

Posted on Feb 18

Understanding the K-th Character in the String Game (Step-by-Step) - LeetCode 3304

#algorithms #leetcode #programming #tutorial

Problem Summary

Alice and Bob are playing a game. Initially, Alice has a string word = "a".

You are given a positive integer k.

Now Bob will ask Alice to perform the following operation forever:

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 enough operations have been done for word to have at least k characters.

Example 1:

Input: k = 5

Output: "b"

Explanation:

Initially, word = "a". We need to do the operation three times:

Generated string is "b", word becomes "ab".
Generated string is "bc", word becomes "abbc".
Generated string is "bccd", word becomes "abbcbccd".

Example 2:

Input: k = 10

Output: "c"

Constraints:

1 <= k <= 500

We start with:

word = "a"

Each operation transforms the string like this:

new_word = old_word + shifted(old_word)

Where shifted(old_word) means each character moves to the next
alphabet letter:

'a' → 'b'
'b' → 'c'
...
'z' → 'a' (wrap around)

The string length doubles every step:

1 → 2 → 4 → 8 → 16 → ...

We must return the k-th character without building the full string.

🧠 Key Insight

At every stage:

S(n) = S(n-1) + shifted(S(n-1))

Which means:

First half → previous string
Second half → shifted(previous string)

So any index k must either:

Be in the first half → same index in previous stage
Be in the second half → map to (k - half) in previous stage, then shift +1

✅ Recursive Implementation

public class Solution {
    public char KthCharacter(int k) {
        return Solve(k);
    }

    private char Solve(int k) {
        if (k == 1) return 'a';

        int length = 1;
        while (length < k) {
            length *= 2;
        }

        int half = length / 2;

        char prev = Solve(k - half);
        return (char)('a' + (prev - 'a' + 1) % 26);
    }
}

🔍 Step-by-Step Example (k = 6)

Step 1

Smallest power of 2 ≥ 6 → 8
Half = 4

6 > 4 → second half
Call Solve(6 - 4) → Solve(2)

Step 2

Smallest power of 2 ≥ 2 → 2
Half = 1

2 > 1 → second half
Call Solve(2 - 1) → Solve(1)

Step 3

Solve(1) → return 'a'

Unwinding

Solve(2): 'a' → shift → 'b'

Solve(6): 'b' → shift → 'c'

✅ Final Answer: 'c'

🧠 What's Happening in Memory

Call stack during execution:

Solve(6)
  → Solve(2)
      → Solve(1)

As recursion unwinds:

Solve(1) returns 'a'
Solve(2) returns 'b'
Solve(6) returns 'c'

Each time we were in the second half, we applied one shift.

⏱ Time & Space Complexity

Time: O(log k)
Space: O(log k) (due to recursion stack)

🔥 Final Takeaway

We never build the full string.

Instead, we:

Keep reducing k
Track how many times we land in the second half
Shift the base character 'a' accordingly

This is classic divide-and-conquer recursion.

If this helped you understand recursion better, try implementing the
iterative version next for even better performance.

DEV Community