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:
-
0means append a copy of the current string. -
1means 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:
-
kto track position from the right half to the left. - A counter
increasesto 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
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/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.