Algorithm

Find the K-th Character

Solution
class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        def get_char(k_val, op_index):
            if k_val == 1:
                return 0
            
            half_size = 1
            while half_size * 2 < k_val:
                half_size *= 2
                
            if k_val <= half_size:
                return get_char(k_val, op_index - 1)
                
            shift = operations[op_index - 1]
            return (get_char(k_val - half_size, op_index - 1) + shift) % 26
            
        return chr(ord('a') + get_char(k, len(operations)))

Time Complexity

O(log K) or O(M)

Space Complexity

O(1)