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

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 simu…


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


Print Share Comment Cite Upload Translate Updates
APA

Om Shree | Sciencx (2025-07-04T01:51:04+00:00) 🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript). Retrieved from https://www.scien.cx/2025/07/04/%f0%9f%8e%ae-beginner-friendly-guide-find-the-k-th-character-in-string-game-ii-leetcode-3307-c-python-javascript/

MLA
" » 🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript)." Om Shree | Sciencx - Friday July 4, 2025, https://www.scien.cx/2025/07/04/%f0%9f%8e%ae-beginner-friendly-guide-find-the-k-th-character-in-string-game-ii-leetcode-3307-c-python-javascript/
HARVARD
Om Shree | Sciencx Friday July 4, 2025 » 🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript)., viewed ,<https://www.scien.cx/2025/07/04/%f0%9f%8e%ae-beginner-friendly-guide-find-the-k-th-character-in-string-game-ii-leetcode-3307-c-python-javascript/>
VANCOUVER
Om Shree | Sciencx - » 🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript). [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/07/04/%f0%9f%8e%ae-beginner-friendly-guide-find-the-k-th-character-in-string-game-ii-leetcode-3307-c-python-javascript/
CHICAGO
" » 🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript)." Om Shree | Sciencx - Accessed . https://www.scien.cx/2025/07/04/%f0%9f%8e%ae-beginner-friendly-guide-find-the-k-th-character-in-string-game-ii-leetcode-3307-c-python-javascript/
IEEE
" » 🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript)." Om Shree | Sciencx [Online]. Available: https://www.scien.cx/2025/07/04/%f0%9f%8e%ae-beginner-friendly-guide-find-the-k-th-character-in-string-game-ii-leetcode-3307-c-python-javascript/. [Accessed: ]
rf:citation
» 🎮 Beginner-Friendly Guide “Find the K-th Character in String Game II” – LeetCode 3307 (C++ | Python | JavaScript) | Om Shree | Sciencx | https://www.scien.cx/2025/07/04/%f0%9f%8e%ae-beginner-friendly-guide-find-the-k-th-character-in-string-game-ii-leetcode-3307-c-python-javascript/ |

Please log in to upload a file.




There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.