題目敘述
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**5n <= 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
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)
}
}