Smallest String With A Given Numeric Value - Leetcode Solution

Problem statement:

You are given two integers n and k. You want to construct a string s of length n using only lower-case English letters such that each letter in s has a numeric value of at least k.

You are allowed to re-use letters in the string, meaning that there can be multiple occurrences of the same letter.

Return the lexicographically smallest string s possible.

Solution:

The approach to solution of this problem is to determine a pattern and to use it to construct the smallest string s possible.

We can use the fact that the alphabetical order of the lower-case English letters is lexicographically increasing. This means that if we fix the first letter of the string s, we can choose the subsequent letters in such a way that the string s remains lexicographically smallest.

We observe that each letter has a numeric value, which is its position in the alphabet starting from a=1 and ending at z=26. This means that the numeric value of a letter can be determined by subtracting 96 from its ASCII value.

We can use the fact that the summation of the numeric values of the letters in s is equal to n * k, where n is the length of the string s and k is the minimum numeric value of any letter in s.

We start by setting the first letter in s to 'a'. This is the lexicographically smallest letter. We can set the numeric value of this letter to k.

We then calculate the remaining numeric value that we need to achieve the required sum n * k. We keep track of this remaining value in a variable called total.

We then iterate over the remaining positions in s from left to right. At each position, we compute the maximum possible numeric value that we can use without exceeding the total.

The maximum value we can use is min(total, 26 - (k + i - 1)). The variable i represents the position that we are currently at in the string. We subtract (k + i - 1) from 26 because we have already used (k + i - 1) characters before the current position and we cannot reuse them.

We append the letter corresponding to the computed numeric value to s and subtract the numeric value from the total. We set k to 1 for all positions after the first one because we have already used the smallest possible value 'a' at the first position.

When we have exhausted all positions in s, we return it as the answer.

Time Complexity:

The time complexity of this algorithm is O(n) because we have to iterate over all positions in the string once.

Space Complexity:

The space complexity of this algorithm is O(n) because we have to store the computed string.

Code:

Here is the Python code for the solution:

class Solution: def getSmallestString(self, n: int, k: int) -> str: s = ["a"] * n total = k - n i = n - 1 while total > 0: max_val = min(total, 26 - (k - (i + 1))) s[i] = chr(max_val + 96) total -= max_val i -= 1 return "".join(s)

1