Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Each operation doubles the word. At operation i, the lower half is unchanged and the appended half either copies it or shifts its letters. In a zero-based position, bit i tells us whether its ancestry passed through that appended half. Only those set bits can contribute a character shift.

Approach

Subtract one from k and inspect its binary digits. Python first determines the bit length and tests each bit; JavaScript extracts successive digits using remainder and integer division by two. For every set bit at index i, add operations[i] to a shift counter. A type-zero operation contributes nothing, while a type-one operation advances the inherited character once.

All positions descend from the initial a, so return a shifted by the total modulo 26. Operations beyond the highest set bit cannot affect this position because it remains in their unchanged first halves. For k = 1, there are no set bits and the result is a. The word itself is never constructed.

class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        k -= 1
        # bit = k.bit_length()
        num = k
        bits = 0

        while num:
            num //= 2
            bits += 1

        res = 0

        for i in range(bits):
            if (k >> i) & 1:
                res += operations[i]

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

Complexity analysis

Time is O(log(k + 1)), including constant work when k = 1. Auxiliary space is O(1) under the stated bounds: k uses at most 47 bits, and JavaScript's arithmetic digit extraction avoids 32-bit bitwise truncation. Neither version constructs the word or scans unused operations.