Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

The requested position is small enough to construct the generated word directly. Each operation preserves the existing prefix and appends a copy with every character advanced by one, so later operations cannot change a position that already exists.

Approach

Start with a character array containing a. While its length is less than k, copy the current array, advance each character in the copy to the next letter, wrapping z to a, and append the transformed copy to the original array.

Once the array is long enough, return index k - 1 because the requested position is one-based. Copying before transformation prevents the original half from being changed. Each iteration doubles the length, and the final length is less than twice k except for the immediate k = 1 case, so constructing the required prefix uses linear total work in k.

class Solution:
    def kthCharacter(self, k: int) -> str:
        res = ['a']

        while len(res) < k:
            curr = res[:]
            for i in range(len(curr)):
                if curr[i] == 'z':
                    curr[i] = 'a'
                else:
                    curr[i] = chr(ord(curr[i]) + 1)
            res += curr

        return res[k - 1]

Complexity analysis

Let k be the requested position. Time: O(k). Auxiliary space: O(k) for the explicitly generated character array.