Python | Easy to understand | Explained
Key idea in my solution can be expressed by a simple example:\n\n\ne.g. Let\'s say there are 2 "V"s and 3 "H"s in the final string.\nQ: How many strings are sma
Key idea in my solution can be expressed by a simple example:\n\n\n**e.g.** Let\'s say there are 2 "V"s and 3 "H"s in the final string.\n**Q:** How many strings are smaller than, e.g., "VHHVH"?\n\n**A:** Obviously the smallest one in this case is "HHHVV", focusing on the "V" which is pulled to the beginning now, if it isn\'t there, then there are C(4,2) = 6 (4 spots for 2 "V"s) strings smaller than "VHHHV". Next looking at the 2nd "V", if it isn\'t pulled to the higher position, then there is C(1,1) = 1 (1 spot for 1 "V") string smaller than "_ _ _ VH". So totally 6 + 1 = 7 strings are smaller than "VHHHV", indicating it the 8th smallest string.\n\t  \n\t  \nTo find the specific string given a number k is pretty much the same idea, but reversely.\n\n\n```\nclass Solution:\n    def kthSmallestPath(self, destination: List[int], k: int) -> str:\n        \n        m, n = destination\n        base = ["H" for i in range(m+n)] \n        t = k-1 # num of instructions smaller than the kth smallest one\n        v_left = m # how many "V" left to be put to the right side\n        \n        \n        for i in range(m+n):\n            if comb(m+n-i-1, v_left) <= t:\n                base[i] = "V"\n                t -= comb(m+n-i-1, v_left)\n                v_left -= 1\n\n                \n            #if t == 0, that means the left "V" should all be put to the rightmost places\n            if t == 0:\n                for j in range(m+n-v_left, m+n):\n                    base[j] = "V"\n                break\n        \n        return "".join(base)\n        \n        ```
['Python']