Problem of The Day: Find the K-th Character in String Game I

Problem Statement

leetcode problem link

Brute Force [Accepted]

class Solution:
    def kthCharacter(self, k: int) -> str:
        word = deque([0])
        while True:
            generated_word = deque()
            original_word = deque()
            while word:
                x = word.popleft()
                original_word.append(x)
                generated_word.append((x + 1) % 26)
            word.extend(original_word)
            word.extend(generated_word)
            if len(word) >= k:
                break
        val = word[k - 1]
        return chr(val + ord('a'))

Editorial

Approach: Iteration

class Solution:
    def kthCharacter(self, k: int) -> str:
        ans = 0
        while k != 1:
            t = k.bit_length() - 1
            if (1 << t) == k:
                t -= 1
            k -= 1 << t
            ans += 1
        return chr(ord("a") + ans)