[C++] Single-pass Solution Explained, ~100% Time, ~98% Space
Alright: while this problem might tempt you to actually compute all/some permutations, the size of the expected string is such that it should definitely make us
Alright: while this problem might tempt you to actually compute all/some permutations, the size of the expected string is such that it should definitely make us very wary about how to proceed in terms of performance.\n\nBut we can go through an actually smarter way, once we figure out that you average result will have a series of initial `\'a\'`s, a central character of some sort and the rest followed by `\'z\'`s, since that is how you get the least lexicographic order out of the given requirements.\n\nTo do so, we will start with 2 support variables:\n* `res`, already initialised to be of the right size in order to avoid painful and expensive reallocation as it would otherwise grow;\n* `i`, our pointer, initially set to address the last cell of `res`.\n\nWe will then start from the right (much more convenient to think that way, IMHO, but feel free to prove me wrong with better ideas!) and we will assign as many characters as we can to be `\'z\'`s, and at the same time reducing `k` by the same amount (`\'z\' == 26`, for this problem), stopping only when we do not have enough "score" to put any more.\n\nTime then to figure out the central character, if any: this will be possible only when `k > i` (since `i` represents how many characters we have left, with `k == i`, it would mean that we can just assign  `\'a\'` to all of them) and we will proceed in a similar fashion:\n* we will reduce `k` by the appropriate value (`i + 1`);\n* assign the result of it to `res[i--]`, incremented by `\'a\'` to make it work.\n\nFinally, one last loop that we know will end up just blindly assigning `\'a\'`s to the remaining `i` characters, since we know for sure now that `k == i`.\n\nOnce done, we can return `res` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    string getSmallestString(int n, int k) {\n        // support variables\n        string res(n, \'*\');\n        int i = n - 1;\n        // getting rid of the largest "load"\n        while (k - 26 > i) {\n            k -= 26;\n            res[i--] = \'z\';\n        }\n        // possible central character\n        if (i < k) res[i--] = \'a\' + (k -= i + 1);\n        // \'a\'s to the end of the world and beyond!\n        while (i > -1) res[i--] = \'a\';\n        return res;\n    }\n};\n```
['C', 'Combinatorics', 'Probability and Statistics', 'C++']