1
# Runtime: 1870 ms (Top 22.43%) | Memory: 15.5 MB (Top 41.47%)
2
class Solution:
3
    def getSmallestString(self, n: int, k: int) -> str:
4
        ans = ["a"] * n  # Initialize the answer to be 'aaa'.. length n
5
        val = n  # Value would be length as all are 'a'
6

7
        for i in range(n - 1, -1, -1):
8
            if (
9
                val == k
10
            ):  # if value has reached k, we have created our lexicographically smallest string
11
                break
12
            val -= 1  # reduce value by one as we are removing 'a' and replacing by a suitable character
13
            ans[i] = chr(
14
                96 + min(k - val, 26)
15
            )  # replace with a character which is k - value or 'z'
16
            val += (
17
                ord(ans[i]) - 96
18
            )  # add the value of newly appended character to value
19

20
        return "".join(ans)  # return the ans string in the by concatenating the list