Python O(logn) Binary Search solution, faster than 91%, explained.
If you think it through or see enough cases, you\'ll find this important pattern: \nThe solution is always formed by a bunch of \'a\'s, a bunch of \'z\'s and AT
If you think it through or see enough cases, you\'ll find this important pattern: \n**The solution is always formed by a bunch of \'a\'s, a bunch of \'z\'s and AT MOST ONE character that is neither \'a\' or \'z\'.**\nIf you could not think it through, just do it reversely, if you have a solution for some case which contains two characters that is neither \'a\' or \'z\', you can either transform these two characters to a \'a\'-and-\'z\' combination or a \'some character less than before\'-and-\'z\' combination, either way the solution is better than the previous one.\n\nAccordingly, the problem is transformed to finding the most \'a\' we can put into the solution, then for the remaining empty positions we fill them with \'z\'s until we couldn\'t, then fill the last one with proper character if needed.\n\nSo the algorithm is done in 3 steps:\n1. find how many (most) \'a\'s we can have with binary search, let\'s say the number is ```x```.\n2. calculate how many (most) \'z\'s we can have to fill ```k - x```, let\'s say this number is ```y```.\n3. if ```x + 26 * y``` doesn\'t add up to k (which also means there is an extra position in the solution), fill the character ```k - (x + 26 * y)``` in the middle.\n\n(Feel free to leave comments if there\'s anything confusing. If you like my solution, please upvote!~)\n\n```python\nclass Solution:\n    def getSmallestString(self, n: int, k: int) -> str:\n        l, r = 0, n\n        while l <= r:\n            mid = l + (r - l) // 2\n            if k - mid > 26 * (n - mid):\n                r = mid - 1\n            elif k - mid == 26 * (n - mid):\n                return \'a\' * mid + \'z\' * (n - mid)\n            elif k - mid < 26 * (n - mid):\n                l = mid + 1\n        \n        if l - 1 >= n:\n            return \'a\' * n\n        l = l - 1\n        \n        num_z = (k - l) // 26\n        c = chr(ord(\'a\') - 1 + k - l - num_z * 26)\n        return \'a\' * l + c + \'z\' * num_z\n```
[]