[Python] O(n) math solution, explained
In this problem we need to construct lexicographically smallest string with given properties, and here we can use greedy strategy: try to take as small symbol a
In this problem we need to construct **lexicographically smallest string** with given properties, and here we can use **greedy** strategy: try to take as small symbol as possible until we can. Smallest letter means `a`, so our string in general case will look like this:\n\n`aa...aa?zz...zz`,\n\nwhere some of the groups can be empty. Now question what is the biggest numbers of `a` we can take. Denote this number by `p` and by `q` we denote value of `?` symbol. Then we have the following equation:\n`p * 1 + q + 26*(n - p - 1) = k`, which is equivalent to:\n`p = (26*n - k + q - 26)/25`.\n\nWe need to find the biggest possible value of `p`: we want as much `a` symbols at the beginning of our string as possible. Value of `q` is not equal to `26`, because then we put it to group of `z` in the end, so we can estimate `p` as:\n`p <= (26*n - k - 1)//25`. From the other side, we always can take `p = (26*n - k - 1)//25`, because we have `n - p` places left with total sum `k - p` and it is enough to show that `(n-p)*26 >= (k-p)`. One more point, given `p` can be negative, so we return `0` in this case.\n\nFinally, we can evaluate `q` as `k - 26*n + 25*p + 26` and get corresponing symbol.\n\n**Complexity**: it is still `O(n)` however, because we need to construct string in the end, what a pity. Space complexity is also `O(n)`.\n\n```\nclass Solution:\n    def getSmallestString(self, n, k):\n        p = max(0, (26*n - k - 1)//25)\n        q = k - 26*n + 25*p + 26\n        return "a"*p + chr(96 + q) + "z"*(n-p-1)\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Greedy']