https://leetcode.com/problems/kth-smallest-instructions

Actualy, I was suprised, why this problem is marked as Hard: all you need to do is to on each moment of time see how many options we have if we go to the right and if we can afford this step or no. If we are out of options, that is k = 1, then we build the rest of the sequence either with H or with V.

Complexity: time complexity is O((m+n)^2) for time: we use comb() function O(m+n) times, where complexity of each evaluation is O(m+n) as well. Space complexity is O(1).

class Solution:
    def kthSmallestPath(self, destination, k):
        m, n, ans = destination[0], destination[1], ""
        for i in range(m+n):
            if k == 1:  #no options left
                ans += "H"*n + "V"*m
                break

            if k <= comb(m+n-1, m):
                n -= 1
                ans += "H"
            else:
                ans += "V"
                k -= comb(m+n-1, m)
                m -= 1
                
        return ans

If you like the solution, you can upvote it on leetcode discussion section: Problem 1643