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)
}
}