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 和 k，需要找出一個字串，然後其長度是 n，然後其字母總和是 k。而字母的值就是相當於字母的順序，例如 a 是 1、b 是 2，依序到 z 是26。而且其最後的字串需要是最小字母排序字串。

解法解析

這題因為需要有字母的數字，慢慢手刻一個 hashmap 可以做到，但是太麻煩了。所以就可以想到的是 ASCII Table 的字母值。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

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

/**
 * @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

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