https://leetcode.com/problems/find-the-k-th-character-in-string-game-i/?envType=daily-question&envId=2025-07-03

initial

correct brute force approach

class Solution:
    def kthCharacter(self, k: int) -> str:
        word="a"
        while len(word)<k:
            tmp=""
            for c in word:
                if ord(c)+1>ord('z'):
                    tmp+='a'
                else:
                    tmp+= chr(ord(c)+1)
            word+=tmp
            tmp=""
        return word[k-1]
            
        

sol much better

Using 1-indexed, once we reach a base case of when of string is 1, thats a. Then according to the position of k, first half of string is the original string while the second half is the transformed string. If the position is in the second half, we need to translate the position by subtracting the half_length of string and transfrom it.

This is cuz if string length=4, half_length=2, k=3 generation=2, the next recursion should search for position 1, cuz generation=1 will have string length of 2 and we should look for position 1, not 3. So k-half_length.

import math
class Solution:
    def kthCharacter(self, k: int) -> str:
        word="a"
        count=1
        tmp=0
        while count<k:
            count*=2
            tmp+=1
        print(tmp)

        def transform(c):
            return chr((ord(c)+1-ord('a'))%26 +ord('a'))

        def find(position,generation):
            if generation==0:
                return 'a'
            half_length=2**(generation-1)
            if position<=half_length:
                return find(position,generation-1)
            else:
                charac = find(position-half_length,generation-1)
                return transform(charac)

        return find(k,tmp)

complexity

log k time
1 space (NOPE) we are using recursion and recursion depth is the number of generations (k) so space is log k