[Leetcode] 3307. Find the K-th Character in String Game II

https://leetcode.com/problems/find-the-k-th-character-in-string-game-ii/description/

initial

so coming from https://velog.io/@whitehousechef/Leetcode-3304.-Find-the-K-th-Character-in-String-Game-I
this q was v similar

class Solution:
    def kthCharacter(self, k: int, operations: List[int]) -> str:
        # 0,1,0,1
        # a                         (no transform)
        # 0-> aa                    (no transform)
        # 1-> aabb                  (no transform)
        # 0-> aabb|aabb             (no transform)    
        # 1-> aabb aabb | bbcc bbcc (transform +1)

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

        total_length = 2**(len(operations))
        def find(position,generation):
            if generation==0:
                return "a"
            half_length = 2**(generation-1)
            if position<=half_length:
                return find(position,generation-1)
            else:
                if operations[generation-1]:
                    character = find(position - half_length,generation-1)
                    return transform(character)
                else:
                    return find(position - half_length,generation-1)

        answer = find(k,len(operations))
        return answer

sol (bit way)

this k position in bit holds information about whether it is in the right or left of the half bit position. If it is 1, then it is right side and else vice versa.

Then we need to & with the operations cuz if operation is 1, then we need to transform. But where does this right or left position matter?

Generation i: [a, b, c, d]
↓
Operation = 1: [a, b, c, d] + [b, c, d, e] ← RIGHT half got +1

The Logic: we only transform if the position is right side (i.e. bit i=1), so thats when we add +v

if k & (1 << i):  # If bit i = 1 (RIGHT half)
    res += v       # Add the operation value

    def kthCharacter(self, k: int, A: List[int]) -> str:
        res = 0
        k -= 1
        for i, v in enumerate(A):
            if k & (1 << i):
                res += v
        return chr(ord('a') + res % 26)

complexity

bit is n time
my way is 2**n time where n=len(opeartions)

space is recursion depth so log n
bit is 1