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

Source: Dev.to

Problem Summary

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

word = "a"

You are given a positive integer k.

Bob repeatedly asks 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.

Examples of the operation

• "c" → "cd"
• "zb" → "zbac"

Return the value of the k‑th 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

word = "a"
1st operation:  generate "b"   → word = "ab"
2nd operation:  generate "bc"  → word = "abbc"
3rd operation:  generate "bccd"→ word = "abbcbccd"

The 5‑th character is 'b'.

Example 2

Input: k = 10
Output: "c"

Constraints

1 ≤ k ≤ 500

Each operation transforms the string as

new_word = old_word + shifted(old_word)

where shifted(old_word) means every character moves to the next alphabet letter ('a' → 'b', …, 'z' → 'a').
The length doubles each step: 1 → 2 → 4 → 8 → 16 → ….
We must obtain the k‑th character without building the full string.

---

🧠 Key Insight

At every stage

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

• First half → previous string S(n‑1)
• Second half → shifted(S(n‑1))

Thus for any index k:

• If k lies in the first half, the character is the same as at index k in the previous stage.
• If k lies in the second half, map it to (k – half) in the previous stage and then shift the resulting character by +1 (mod 26).

---

✅ Recursive Implementation (Java)

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

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

        // Find the smallest power of two ≥ k
        int length = 1;
        while (length > 1;    // half = length / 2

        // k is in the second half → recurse on the mirrored index
        char prev = solve(k - half);
        // shift by one position in the alphabet (wrap around at 'z')
        return (char)('a' + (prev - 'a' + 1) % 26);
    }
}

The recursion stops when k == 1, returning the base character 'a'.
Each time we fall into the second half we apply one alphabetic shift.

---

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

Unwinding

• solve(2): 'a' shifted → 'b'
• solve(6): 'b' shifted → 'c'

Result: 'c'

---

🧠 What’s Happening in Memory

Call stack for k = 6:

solve(6)
  → solve(2)
      → solve(1)

As the recursion unwinds, each return from a second‑half call adds one alphabetic shift, producing the final character.

---

⏱ Time & Space Complexity

• Time: O(log k) – each recursive step halves the problem size.
• Space: O(log k) – recursion stack depth.

---

🔥 Final Takeaway

We never construct the full string. By repeatedly reducing k and counting how many times we land in the second half, we can compute the required character with a simple divide‑and‑conquer recursion (or an equivalent iterative version). This approach runs in logarithmic time and uses only logarithmic auxiliary space.