Code Implementation

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        res = ['a'] * n
        k -= n  # since each 'a' already contributes 1
        idx = n - 1
        while k > 0:
            add = min(25, k)
            res[idx] = chr(ord('a') + add)
            k -= add
            idx -= 1
        return ''.join(res)
      

class Solution {
public:
    string getSmallestString(int n, int k) {
        string res(n, 'a');
        k -= n;
        int idx = n - 1;
        while (k > 0) {
            int add = min(25, k);
            res[idx] = 'a' + add;
            k -= add;
            idx--;
        }
        return res;
    }
};
      

class Solution {
    public String getSmallestString(int n, int k) {
        char[] res = new char[n];
        for (int i = 0; i < n; i++) res[i] = 'a';
        k -= n;
        int idx = n - 1;
        while (k > 0) {
            int add = Math.min(25, k);
            res[idx] = (char)('a' + add);
            k -= add;
            idx--;
        }
        return new String(res);
    }
}
      

var getSmallestString = function(n, k) {
    let res = Array(n).fill('a');
    k -= n;
    let idx = n - 1;
    while (k > 0) {
        let add = Math.min(25, k);
        res[idx] = String.fromCharCode('a'.charCodeAt(0) + add);
        k -= add;
        idx--;
    }
    return res.join('');
};
      

Problem Description

Given two integers n and k, your task is to construct the lexicographically smallest string of length n using only lowercase English letters ('a' to 'z'), such that the sum of the numeric values of its characters is exactly k. The numeric value of a letter is its position in the alphabet (i.e., 'a' = 1, 'b' = 2, ..., 'z' = 26).

• Each character can be used any number of times.
• There is always exactly one valid solution for each input.
• You cannot reuse positions, but you can use the same character in multiple positions.

Thought Process

At first glance, the problem seems to ask for the smallest possible string (alphabetically) whose letters add up to a given value. The brute-force way would be to try all possible combinations, but that is clearly inefficient for large n and k.

To minimize the string lexicographically, we should put the smallest letters ('a') at the front as much as possible. If we need larger values to reach k, we should place them at the end so that the beginning of the string remains as small as possible.

The key realization is that we can "fill" the string from the end with the largest possible letters (up to 'z'), using 'a' by default, and only increase the value of the last few letters as needed to reach the target sum.

Solution Approach

• Start by filling the string with 'a' in all n positions. This gives a starting sum of n (since each 'a' is worth 1).
• Calculate the remaining value we need to reach k: remaining = k - n.
• Starting from the end of the string, for each position, we can increase the letter from 'a' up to 'z' (which means adding up to 25 to the value at that position).
• For each position from right to left, add as much as possible (up to 25) without exceeding the remaining value. Update the character accordingly.
• Continue until the remaining value is zero.
• Return the constructed string.

This approach ensures that the string is as small as possible lexicographically, since any larger letters are pushed to the end.

Example Walkthrough

Let's walk through an example with n = 5 and k = 73:

1. Start with res = ['a', 'a', 'a', 'a', 'a'] (sum = 5).
2. Remaining = 73 - 5 = 68.
3. From the last position:
   • At index 4 (last): add min(25, 68) = 25. Set res[4] = 'z'. Remaining = 68 - 25 = 43.
   • At index 3: add min(25, 43) = 25. Set res[3] = 'z'. Remaining = 43 - 25 = 18.
   • At index 2: add min(18, 18) = 18. Set res[2] = 'a' + 18 = 's'. Remaining = 0.
4. No more remaining value. Final string: 'aaszz'.
5. Check: 'a' (1) + 'a' (1) + 's' (19) + 'z' (26) + 'z' (26) = 1+1+19+26+26 = 73.

This is the lexicographically smallest string of length 5 with a numeric value of 73.

Time and Space Complexity

• Brute-force approach: Would involve generating all possible strings of length n and checking their values, which is O(26^n) — clearly infeasible for large n.
• Optimized approach (as above):
  • We iterate over the string at most once (from the end to the start), so the time complexity is O(n).
  • We use an array of length n to build the string, so the space complexity is also O(n).

The optimized approach is efficient and works well within the problem's constraints.

Summary

The problem boils down to distributing the required numeric value across the string in a way that keeps it lexicographically smallest. By filling with 'a's and only increasing values from the end as needed, we ensure the smallest possible string. The approach is both simple and efficient, requiring only a single pass and minimal extra space. This method elegantly leverages the properties of lexicographical order and greedy allocation.