# Smallest String With A Given Numeric Value
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/smallest-string-with-a-given-numeric-value)
Canonical: https://scaleengineer.com/dsa/problems/smallest-string-with-a-given-numeric-value
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
**Companies:** [Lendingkart Technologies](https://scaleengineer.com/companies/lendingkart-technologies)
---
## Problem
The **numeric value** of a **lowercase character** is defined as its position `(1-indexed)` in the alphabet, so the numeric value of `a` is `1`, the numeric value of `b` is `2`, the numeric value of `c` is `3`, and so on.

The **numeric value** of a **string** consisting of lowercase characters is defined as the sum of its characters' numeric values. For example, the numeric value of the string `"abe"` is equal to `1 + 2 + 5 = 8`.

You are given two integers `n` and `k`. Return _the **lexicographically smallest string** with **length** equal to `n` and **numeric value** equal to `k`._

Note that a string `x` is lexicographically smaller than string `y` if `x` comes before `y` in dictionary order, that is, either `x` is a prefix of `y`, or if `i` is the first position such that `x[i] != y[i]`, then `x[i]` comes before `y[i]` in alphabetic order.

**Example 1:**

**Input:** n = 3, k = 27
**Output:** "aay"
**Explanation:** The numeric value of the string is 1 + 1 + 25 = 27, and it is the smallest string with such a value and length equal to 3.

**Example 2:**

**Input:** n = 5, k = 73
**Output:** "aaszz"

**Constraints:**

* `1 <= n <= 105`
* `n <= k <= 26 * n`

# Approaches
## Greedy Construction from Left to Right
This approach builds the string from left to right (from the first character to the last). At each position, it greedily chooses the smallest possible character ('a', 'b', 'c', ...) that allows the rest of the string to still form the required numeric sum `k`.
**Time:** O(n), as we iterate through the length of the string once, and all operations inside the loop are constant time. · **Space:** O(n) to store the result string. In Java, `StringBuilder` uses a character array internally, so the space is proportional to the length of the string `n`.
**Pros:** It's a correct greedy algorithm that finds the optimal solution.; It has linear time complexity, which is efficient for the given constraints.
**Cons:** The logic inside the loop is slightly more complex than the right-to-left approach, involving a calculation at each step.; It might be slightly less intuitive to reason about compared to the alternative greedy strategy.
### Explanation
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'.

```java
class Solution {
    public String getSmallestString(int n, int k) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            // remaining length after this character
            int remainingLen = n - 1 - i;
            // The max possible sum for remaining length is remainingLen * 26
            // If we pick a character with value 'val', the remaining sum must be k - val.
            // So, k - val <= remainingLen * 26  => val >= k - remainingLen * 26
            // To get the lexicographically smallest string, we pick the smallest possible val.
            int val = 1;
            if (k - val > remainingLen * 26) {
                val = k - remainingLen * 26;
            }
            sb.append((char) ('a' + val - 1));
            k -= val;
        }
        return sb.toString();
    }
}
```
### Algorithm
- 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.

## Optimized Greedy Construction from Right to Left
This is a more intuitive and elegant greedy approach. The core idea is to make the string's prefix as small as possible (i.e., full of 'a's) and compensate by making the suffix as large as possible. We achieve this by filling the string from right to left with the largest possible values.
**Time:** O(n). We have one pass to fill the array with 'a's and another pass to adjust the characters from right to left. This is `O(n) + O(n) = O(n)`. · **Space:** O(n) to store the character array for the result.
**Pros:** Very intuitive and easy to understand.; The implementation is simple and clean.; Optimal time and space complexity.; Generally faster in practice due to simpler logic in the loop.
**Cons:** This implementation uses two passes (one to fill with 'a's, one to modify), but this is a minor point as the overall complexity remains linear.
### Explanation
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'.

```java
import java.util.Arrays;

class Solution {
    public String getSmallestString(int n, int k) {
        char[] result = new char[n];
        Arrays.fill(result, 'a');
        k -= n; // Initial sum is n, we need to add k-n more

        for (int i = n - 1; i >= 0; i--) {
            if (k == 0) {
                break;
            }
            int add = Math.min(k, 25);
            result[i] = (char) (result[i] + add);
            k -= add;
        }
        return new String(result);
    }
}
```
### Algorithm
- 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.

# Solutions
### Java

```java
class Solution { public String getSmallestString ( int n , int k ) { char [] ans = new char [ n ]; Arrays . fill ( ans , 'a' ); int i = n - 1 , d = k - n ; for (; d > 25 ; d -= 25 ) { ans [ i --] = 'z' ; } ans [ i ] = ( char ) ( 'a' + d ); return String . valueOf ( ans ); } }
```

### CPP

```cpp
class Solution { public: string getSmallestString ( int n , int k ) { string ans ( n , 'a' ); int i = n - 1 , d = k - n ; for (; d > 25 ; d -= 25 ) { ans [ i -- ] = 'z' ; } ans [ i ] += d ; return ans ; } };
```

### Python

```python
class Solution : def getSmallestString ( self , n : int , k : int ) -> str : ans = [ 'a' ] * n i , d = n - 1 , k - n while d > 25 : ans [ i ] = 'z' d -= 25 i -= 1 ans [ i ] = chr ( ord ( ans [ i ]) + d ) return '' . join ( ans )
```