# LeetCode Solution, Medium, 1663. Smallest String With A Given Numeric Value

# [1663. Smallest String With A Given Numeric Value](https://leetcode.com/problems/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` 和 `k`，需要找出一個字串，然後其長度是 `n`，然後其字母總和是 `k`。而字母的值就是相當於字母的順序，例如 `a` 是 `1`、`b` 是 `2`，依序到 `z` 是26。而且其最後的字串需要是最小字母排序字串。

## 解法解析

這題因為需要有字母的數字，慢慢手刻一個 hashmap 可以做到，但是太麻煩了。所以就可以想到的是 [ASCII Table](https://www.cs.cmu.edu/~pattis/15-1XX/common/handouts/ascii.html) 的字母值。`a` 到 `z`，分別是 97 ~ 122，所以只要減去 96 就可以得到值了。

再來是解題思維，因為我們想要找到最小的**最小字母排序字串**。舉個例子，今天 `k` 是 32 的話，答案可以是 `aaey` 或 `aadz`，但是因為要是最小字母排序字串，所以前面要盡可能的小，因此答案只能是 `aadz`。因為要盡可能的小，所以我們可以先把字串全部的值都設定為 `a`，而剩餘的值從最後一位盡量取最大值。

`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

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

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

#### JavaScript

```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);
        k -= add;
    }
    return result.join('');
};
```

#### Kotlin

```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

```php
```

#### Python

```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)
            k -= add
        return ''.join(result)
```

#### Rust

```rust
```

#### Swift

```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)!)
            diff -= add
        }
        return String(result)
    }
}
```