https://leetcode.com/problems/smallest-string-with-a-given-numeric-value

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:

aa...aa?zz...zz,

where 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: p * 1 + q + 26*(n - p - 1) = k, which is equivalent to: p = (26*n - k + q - 26)/25.

We 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: 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.

Finally, we can evaluate q as k - 26*n + 25*p + 26 and get corresponing symbol.

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).

class Solution:
    def getSmallestString(self, n, k):
        p = max(0, (26*n - k - 1)//25)
        q = k - 26*n + 25*p + 26
        return "a"*p + chr(96 + q) + "z"*(n-p-1)

If you like the solution, you can upvote it on leetcode discussion section: Problem 1663