Find the K-th Character in String Game II
Problem
Start with word = "a". For each value in operations, the string doubles in length. If operations[i] == 0, append a plain copy of word to itself. If operations[i] == 1, append a copy in which every letter is shifted to the next letter of the alphabet (with z wrapping back to a). After all operations, return the k-th character (1-indexed). Since k can be up to 1014, you cannot build the string — trace the position instead.
k = 10, operations = [0,1,0,1]"b"def kthCharacter(k, operations):
pos = k - 1 # convert to 0-indexed position
n = 0 # smallest n with 2^n >= k
while (1 << n) < k:
n += 1
shifts = 0 # total +1 alphabet shifts collected
for i in range(n - 1, -1, -1):
half = 1 << i # length of word before operation i
if pos >= half: # char lives in the appended second half
pos -= half # map back into the first half
if operations[i] == 1:
shifts += 1 # type-1 copy shifted this char once
return chr((shifts % 26) + ord('a'))function kthCharacter(k, operations) {
let pos = k - 1n; // 0-indexed position (BigInt for 1e14)
let n = 0; // smallest n with 2^n >= k
while ((1n << BigInt(n)) < k) n++;
let shifts = 0; // total +1 alphabet shifts collected
for (let i = n - 1; i >= 0; i--) {
const half = 1n << BigInt(i); // length of word before operation i
if (pos >= half) { // char lives in the appended second half
pos -= half; // map back into the first half
if (operations[i] === 1) shifts++; // type-1 copy shifted it once
}
}
return String.fromCharCode((shifts % 26) + 97);
}char kthCharacter(long k, int[] operations) {
long pos = k - 1; // 0-indexed position
int n = 0; // smallest n with 2^n >= k
while ((1L << n) < k) n++;
int shifts = 0; // total +1 alphabet shifts collected
for (int i = n - 1; i >= 0; i--) {
long half = 1L << i; // length of word before operation i
if (pos >= half) { // char lives in the appended second half
pos -= half; // map back into the first half
if (operations[i] == 1) shifts++; // type-1 shifted it once
}
}
return (char) ('a' + shifts % 26);
}char kthCharacter(long long k, vector<int>& operations) {
long long pos = k - 1; // 0-indexed position
int n = 0; // smallest n with 2^n >= k
while ((1LL << n) < k) n++;
int shifts = 0; // total +1 alphabet shifts collected
for (int i = n - 1; i >= 0; i--) {
long long half = 1LL << i; // length of word before operation i
if (pos >= half) { // char lives in the appended second half
pos -= half; // map back into the first half
if (operations[i] == 1) shifts++; // type-1 shifted it once
}
}
return (char) ('a' + shifts % 26);
}Explanation
Each operation doubles the string, so after i operations the length is exactly 2i. That means we never have to materialize the (possibly astronomically long) word — we only need to know which original character position k descends from, and how its letter was changed along the way.
Only the relevant operations matter. Position k first exists once the length reaches k, so we find the smallest n with 2n ≥ k. Operations after the first n just duplicate text far to the right of position k and never touch it, so we ignore them.
Trace the position backwards. Work from operation i = n-1 down to 0. Before operation i the word had length half = 2i. Operation i appended a second copy of that block. If our 0-indexed pos is ≥ half, the character lives in the appended half — so it is a copy of the character at pos - half in the first half. We subtract half to follow it back to its source.
Count the shifts. Whenever we step back across a type-1 append (and the character was in that appended half), the copy had every letter bumped by one, so we add 1 to shifts. The original character is always 'a' (the seed), and 'z' wraps to 'a', so the final answer is simply chr((shifts mod 26) + 'a').
Notice pos ≥ half is exactly testing bit i of k-1: the set bits of k-1 pick out which appends placed the character in a second half, which is why this is a bit-manipulation problem. Example: k = 10, operations = [0,1,0,1] resolves to one type-1 shift, giving 'a' + 1 = 'b'.