Simplest solution with intution | Divide and Conquer approach by checking at every index
Intuition\nIt is pretty obvious, that we need destination[1] \'H\' and destination[0] \'V\'. Lets say we need x number of Hs and y number of Vs. \nSo total poss
# Intuition\nIt is pretty obvious, that we need destination[1] \'H\' and destination[0] \'V\'. Lets say we need x number of Hs and y number of Vs. \nSo total possible arrangements are = $$(x + y)C(x)$$ [combinations] \n\nCan we somehow fix each character of the string one by one and reduce our search space \'k\' ?\n\n# Approach\nSay we build the string s (which is the kth lexographically smallest string) and are currently deciding the whether \'H\' should come first, or \'V\' should come first.\n\nIf H comes first, we have $$(x + y - 1)C(x - 1)$$ possibilities after this char.\n\nSay halfway = $$(x + y - 1)C(x - 1)$$. \n\nSo if we need the kth comb and k <= halfway, then our first char is \'H\' and now we need the second character and we are still searching for the kth smallest string with (x - 1) Hs [because we used up 1 H here] and y Vs.\n\nHowever, say k > halfway, then our first char is \'V\', and now we are searching for the (k - halfway) smallest char in the rest of the string with x Hs and (y - 1) Vs.\n\nThe base cases will be:\n    H == 0 and V == 0: return the string formed so far\n    H == 0: append all left over Vs and return the string\n    V == 0: append all left over Hs and return the string\n\n# Complexity\n- Time complexity:\nLen of string is x + y (ie at max 30). For each string position we do a calc of $$nCr$$.\nThat is of $$O(n)$$ complexity (with n <= 30)\n\nWorst case we do this $$O(n)$$ op n times\nT.C. = $$O(n^2)$$\n\n- Space complexity:\nAlthough we dont use extra space for the main func, the Combinations calculation uses extra $$O(n)$$ space. This is avoidable though and we can solve it in O(1) memory\n\n# Code\n```\n#define ll long long\n\nclass Solution {\npublic:\n    string kthSmallestPath(vector<int>& destination, int k) {\n        int H = destination[1], V = destination[0];\n        string s = "";\n        return helper(H, V, k, s);\n    }\n\nprivate:\n    int comb(int n, int r){\n        if(n == 1) return 1;\n        vector<ll> prev = {1, 1};\n        int x = 2;\n        while(x <= n){\n            vector<ll> curr(x+1);\n            for(int j = 0; j<x+1; j++){\n                if((j==0) || (j == x)) curr[j] = 1;\n                else curr[j] = prev[j]+prev[j-1];\n            }\n            x++;\n            prev = curr;\n        }\n        return prev[r];\n    }\n    \n    string helper(int H, int V, int k, string s) {\n        if(H == 0) {\n            while(V--) s.push_back(\'V\');\n            return s;\n        }\n        if(V == 0) {\n            while(H--) s.push_back(\'H\');\n            return s;\n        }\n\n        int halfway = comb(H + V - 1, H - 1);\n\n        if(halfway >= k) {\n            s.push_back(\'H\');\n            return helper(H - 1, V, k, s);\n        }\n        else {\n            s.push_back(\'V\');\n            return helper(H, V - 1, k - halfway, s);\n        }\n    }\n};\n```
['Divide and Conquer', 'Combinatorics', 'C++']