# 1663. Smallest String With A Given Numeric Value

## 題目敘述

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`

Hint 1:

Think greedily.

Hint 2:

If you build the string from the end to the beginning, it will always be optimal to put the highest possible character at the current index.

## 解法解析

`n = 4, k = 32`

``````result = ['a', 'a', 'a', 'a']
k - n => 剩下 28 要補齊
``````

``````先取 index = n -1 的值 result[3] 補成最大值
k > 26 => 取 26
k < 26 => 取 k
result = ['a', 'a', 'a', 'z']
k - (26 - 1) => 3 (z 到 a 只差 25，所以減 25)
``````

``````取下一個 index = n - 2 的值 result[2]，同第二部將其補上剩餘的值
result = ['a', 'a', 'd', 'z']
``````

### 解法範例

#### Go

``````func getSmallestString(n int, k int) string {
result := make([]byte, n)

for i := n - 1; i >= 0; i-- {
}
result[i] = byte(add + 'a' - 1)
}
return string(result)
}
``````

#### JavaScript

``````/**
* @param {number} n
* @param {number} k
* @return {string}
*/
var getSmallestString = function (n, k) {
const result = Array(n).fill(0);
for (let i = n - 1; i >= 0; i--) {
const add = Math.min(k - i, 26);
result[i] = String.fromCharCode(add + 'a'.charCodeAt(0) - 1);
}
return result.join('');
};
``````

#### Kotlin

``````class Solution {
fun getSmallestString(n: Int, k: Int): String {
val result = CharArray(n) { 'a' }
var remaining = k - n

for (i in result.lastIndex downTo 0) {
val change = if (remaining > 25) 25 else remaining

result[i] = result[i] + change
remaining -= change

if (remaining == 0) break
}

return String(result)
}
}
``````

#### PHP

``````
``````

#### Python

``````class Solution:
def getSmallestString(self, n: int, k: int) -> str:
result = ['a'] * n
for i in range(n - 1, -1, -1):
add = min(k - i, 26)
result[i] = chr(add + ord('a') - 1)
return ''.join(result)
``````

#### Rust

``````
``````

#### Swift

``````class Solution {
func getSmallestString(_ n: Int, _ k: Int) -> String {
var result: [Character] = Array(repeating: "a", count: n), diff = k

for i in stride(from: n - 1, to: -1, by: -1) {
var add = min(diff - i, 26)
result[i] = Character(UnicodeScalar(add + 97 - 1)!)