We’re asked to create a string of size n with a value k where each letter from a - z is valued 1 - 26. The string should be lexicographically smallest, essentially the chatacters should be in increasing order from left to right.
This is a greedy problem, easily solvable by selecting the largest possible character at each location, starting from the right. We create an array of 0’s of size n, then iterate from n - 1 to 0. At each location, we select min(k - i, 26) where i is our current position in the string. This helps us maintain an idea of how many characters are remaining for selection.
After we select a character, we decrement k by the value of the character and store the character in the answer array at the current position.
The solution is as follows:
class Solution:
def getSmallestString(self, n: int, k: int) -> str:
ans = [0] * n
for i in range(n - 1, -1, -1):
char = min(k - i, 26)
k -= char
ans[i] = chr(char + ord('a') - 1)
return "".join(ans)_ Time Complexity:
O(n) - We iterate n times to select n characters.
_ Space Complexity:
O(n) - We store our answer in an array of size n.