# Solutions to Leetcode 1663. Smallest String With A Given Numeric Value

# Problem statement

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 <= 10^5`

.`n <= k <= 26 * n`

.

# Solution 1: Adding each character as small as possible

Construct the result from scratch, from left to right.

For each position, add the smallest possible character.

Let us call the resulting string `s`

.
To compute the smallest possible character for `s[i]`

, you can assume the remaining letters after `s[i]`

are all `z`

.

## Example

For `n = 3, k = 27`

.

- Assume
`s = "?zz"`

. Then`k - "zz" = 27 - 52 = -25 <= 'a'`

. So`s[0]`

can be`'a'`

. - Assume
`s = "a?z"`

. Then`k - "az" = 27 - 27 = 0 <= 'a'`

. So`s[1]`

can be`'a'`

. - Now
`s = "aa?"`

and`k - "aa" = 27 - 2 = 25 = 'y'`

. So`s[2] = 'y'`

. `s = "aay"`

.

## Code

```
#include <iostream>
using namespace std;
string getSmallestString(int n, int k) {
string s;
while (n > 0) {
int i = k - 26*(n - 1); // assume remain letters are all 'z'
char c = i <= 1 ? 'a' : 'a' + i - 1;
s += c;
k -= c - 'a' + 1;
n--;
}
return s;
}
int main() {
cout << getSmallestString(3, 27) << endl;
cout << getSmallestString(5, 73) << endl;
}
```

```
Output:
aay
aaszz
```

## Complexity

- Runtime:
`O(n)`

. - Extra space:
`O(1)`

.

# Solution 2: Adjust the result from `"aa...a"`

You can do the other way around by starting from `s = "aa...a"`

and adjusting each letter `'a'`

from right to left to be the biggest possible.

## Example 2

For `n = 5`

and `k = 73`

:

- Starting with
`s = "aaaaa"`

. `k`

becomes`73 - "aaaaa" = 68`

, which is big enough to make the last`'a'`

becomes`'z'`

:`s = "aaaaz"`

.`k`

becomes`73 - "aaaaz" = 43`

, which is big enough to make the next`'a'`

becomes`'z'`

:`s = "aaazz"`

.`k`

becomes`73 - "aaazz" = 18`

, which make the next`'a'`

becomes`'s'`

:`s = "aaszz"`

.`s = "aaszz"`

.

```
#include <iostream>
#include <string>
using namespace std;
string getSmallestString(int n, int k) {
string s(n, 'a');
k -= n;
while (k > 0 && n > 0) {
if (k > 25) {
s[n - 1] = 'z';
k -= 25;
n--;
} else {
s[n - 1] = 'a' + k;
break;
}
}
return s;
}
int main() {
cout << getSmallestString(3, 27) << endl;
cout << getSmallestString(5, 73) << endl;
}
```

```
Output:
aay
aaszz
```

## Complexity

- Runtime:
`O(n)`

. But it is faster than Solution 1 since there are fewer operations, especially there is no multiplication. - Extra space:
`O(1)`

.