🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript)

This content originally appeared on DEV Community and was authored by Om Shree

Today we dive into String Game II, a fascinating extension of character transformations involving two unique operations. With string doubling and alphabetic increments — plus a huge value of k — this problem becomes a perfect exercise in bit-level simulation and reverse tracking.

Let’s unravel the logic, fast-forward through time, and locate that elusive k-th character!

Problem Summary

You’re given:

• A starting string word = "a"

• A list of operations, where:

  • 0 means append a copy of the current string.
  • 1 means transform each character to its next alphabet and append it.

• A large integer k

Each operation changes the string. Your task is to find the character at position k (1-indexed) after all operations are applied.

Constraints:

• 1 ≤ k ≤ 10^{14} — too large to build the string explicitly.
• At most 100 operations.

Intuition

We cannot afford to simulate the string because it becomes exponentially large.

Observation:
Each operation either:

• Doubles the string size (type 0)
• Appends an “incremented” version of the string (type 1)

If we view the transformation history in reverse, we can trace back where character k came from.

We use:

• k to track position from the right half to the left.
• A counter increases to record how many type-1 operations influenced our character.

Finally, the k-th character must be 'a' + increases % 26.

C++ Code

class Solution {
 public:
  char kthCharacter(long long k, vector<int>& operations) {
    const int operationsCount = ceil(log2(k));
    int increases = 0;

    for (int i = operationsCount - 1; i >= 0; --i) {
      const long halfSize = 1L << i;
      if (k > halfSize) {
        k -= halfSize;  // Move k from the right half to the left half.
        increases += operations[i];
      }
    }

    return 'a' + increases % 26;
  }
};

Python Code

class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        from math import log2, ceil
        operationsCount = ceil(log2(k))
        increases = 0

        for i in reversed(range(operationsCount)):
            halfSize = 1 << i
            if k > halfSize:
                k -= halfSize
                increases += operations[i]

        return chr(ord('a') + increases % 26)

JavaScript Code

var kthCharacter = function(k, operations) {
    const operationsCount = Math.ceil(Math.log2(k));
    let increases = 0;

    for (let i = operationsCount - 1; i >= 0; i--) {
        const halfSize = 1n << BigInt(i);
        if (BigInt(k) > halfSize) {
            k -= Number(halfSize);
            increases += operations[i];
        }
    }

    return String.fromCharCode('a'.charCodeAt(0) + increases % 26);
};

Key Takeaways

• Simulating the string directly is impractical due to exponential growth.
• Reverse the operations to trace character origin.
• Use log2(k) to bound your trace depth.
• Character transformation is tracked using modulo arithmetic.

Final Thoughts

This problem is a powerful lesson in reverse simulation and efficient computation with huge sequences. It emphasizes thinking backwards — a classic trick for problems with growing operations.

Until next time, happy coding!

This content originally appeared on DEV Community and was authored by Om Shree