Smallest String With A Given Numeric Value

• Initialize a StringBuilder or character array res.
• Loop with an index i from 0 to n-1 to build the string from left to right.
• In each iteration, we have n - i characters left to place and a remaining value of k to achieve.
• Calculate the maximum possible sum for the characters to the right of the current one: max_rem_sum = (n - 1 - i) * 26.
• Try to place the smallest character, 'a' (value 1). This is possible only if the remaining value k - 1 can be formed by the rest of the string. The condition is k - 1 <= max_rem_sum.
• If the condition is not met, we must place a larger character. The smallest possible character value v we can place is v = k - max_rem_sum.
• We append the determined character to our result, update k by subtracting the character's value, and continue to the next position.
• After the loop, convert the result to a string.

We iterate from the first position (i = 0) to the last (i = n-1). For each position i, we need to decide which character to place. We have n - i characters left to form a total sum of k.

To make the string lexicographically smallest, we want to use the smallest possible character at the current position i. Let's try to place 'a' (value 1). If we place 'a', the remaining n - i - 1 characters must sum up to k - 1. The maximum possible sum for n - i - 1 characters is (n - i - 1) * 26. So, we can place 'a' only if k - 1 is not more than this maximum possible sum. That is, if k - 1 <= (n - i - 1) * 26.

If this condition holds, we append 'a' to our result, decrease k by 1, and move to the next position.

If the condition does not hold, it means we must place a character larger than 'a' to reduce k sufficiently. The character's value v must satisfy k - v <= (n - i - 1) * 26. To maintain the lexicographically smallest order, we must choose the smallest v that satisfies this, which is v = k - (n - i - 1) * 26. We calculate this value v, find the corresponding character, and append it. After placing this character, the remaining sum required is exactly (n - i - 1) * 26, which means all subsequent characters must be 'z'.

1class Solution {2    public String getSmallestString(int n, int k) {3        StringBuilder sb = new StringBuilder();4        for (int i = 0; i < n; i++) {5            // remaining length after this character6            int remainingLen = n - 1 - i;7            // The max possible sum for remaining length is remainingLen * 268            // If we pick a character with value 'val', the remaining sum must be k - val.9            // So, k - val <= remainingLen * 26  => val >= k - remainingLen * 2610            // To get the lexicographically smallest string, we pick the smallest possible val.11            int val = 1;12            if (k - val > remainingLen * 26) {13                val = k - remainingLen * 26;14            }15            sb.append((char) ('a' + val - 1));16            k -= val;17        }18        return sb.toString();19    }20}

• Create a character array res of size n and initialize all its elements to 'a'.
• This initial string has a numeric value of n. We need to increase this sum by k - n.
• Let k = k - n be the remaining value to distribute among the characters.
• Iterate from the last index i = n-1 down to 0.
• At each position i, the character is 'a' (value 1) and can be increased to 'z' (value 26), which is an increase of at most 25.
• Determine the value to add at the current position: add = min(k, 25).
• Update the character: res[i] = (char)(res[i] + add).
• Decrease k by the added amount: k -= add.
• If k becomes 0, we can stop early as the sum is satisfied.
• After the loop, convert the character array to a string and return it.

To get the lexicographically smallest string, we want as many 'a's at the beginning as possible. We can start by assuming the entire string is composed of 'a's. This gives a string of length n with the minimum possible numeric value, which is n.

The required numeric value is k. We have a deficit of k - n that we need to add to the string's value. To keep the prefix of the string as small as possible, we should add this deficit to the characters at the end of the string first, making them as large as possible.

We iterate from the last character (i = n-1) backwards to the first (i = 0). At each position i, the character is currently 'a' (value 1). The maximum value it can have is 'z' (value 26). So, we can increase its value by at most 25. Let remaining_k = k - n. For the character at position i, we add min(remaining_k, 25) to its value. We update the character at result[i] and subtract the added value from remaining_k. We repeat this process, moving leftwards, until remaining_k becomes zero. The characters that are not modified remain 'a'.

1import java.util.Arrays;2 3class Solution {4    public String getSmallestString(int n, int k) {5        char[] result = new char[n];6        Arrays.fill(result, 'a');7        k -= n; // Initial sum is n, we need to add k-n more8 9        for (int i = n - 1; i >= 0; i--) {10            if (k == 0) {11                break;12            }13            int add = Math.min(k, 25);14            result[i] = (char) (result[i] + add);15            k -= add;16        }17        return new String(result);18    }19}