1643. Kth Smallest Instructions - cocoder39/coco39_LC GitHub Wiki

1643. Kth Smallest Instructions

comb(N, K) = N! / ((N-K)! * K!)

class Solution:
    def kthSmallestPath(self, destination: List[int], k: int) -> str:
        from math import comb
        down, right = destination
        
        sequence = []
        remain_down = down
        for i in range(down+right):
            remain = down + right - (i + 1)
            com = comb(remain, remain_down) # the num of remaining sequences if putting a `H` here
            if com >= k:
                sequence.append('H')
            else:
                remain_down -= 1
                k -= com                
                sequence.append('V')
        return ''.join(sequence)