[LeetCode] 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 <= 105
n <= k <= 26 * n

具有给定数值的最小字符串。

小写字符的数值是它在字母表中的位置（从 1 开始），因此 a 的数值为 1 ，b 的数值为 2 ，c 的数值为 3 ，以此类推。

字符串由若干小写字符组成，字符串的数值为各字符的数值之和。例如，字符串 "abe" 的数值等于 1 + 2 + 5 = 8 。

给你两个整数 n 和 k 。返回长度等于 n 且数值等于 k 的字典序最小的字符串。

注意，如果字符串 x 在字典排序中位于 y 之前，就认为 x 字典序比 y 小，有以下两种情况：

x 是 y 的一个前缀；
如果 i 是 x[i] != y[i] 的第一个位置，且 x[i] 在字母表中的位置比 y[i] 靠前。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/smallest-string-with-a-given-numeric-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是贪心。题意是请你拼接成一个字典序最小的字符串，那么这个字符串的开头需要尽量都是a才行；这个条件反过来理解就是 K 尽量摆到字符串的末端。因为要求组成的字符串的长度 n 已经给定，所以我们创建一个长度为n的char array，并且每个位置上一开始初始化一个'a'。接着我们从后往前试图把剩下的值累加到每个位置上即可。

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public String getSmallestString(int n, int k) {
 3         char[] res = new char[n];
 4         Arrays.fill(res, 'a');
 5         k -= n;
 6         for (int i = res.length - 1; i >= 0; i--) {
 7             res[i] += Math.min(25, k);
 8             k -= Math.min(25, k);
 9             if (k <= 0) {
10                 break;
11             }
12         }
13         return String.valueOf(res);
14     }
15 }

JavaScript实现

 1 /**
 2  * @param {number} n
 3  * @param {number} k
 4  * @return {string}
 5  */
 6 var getSmallestString = function (n, k) {
 7     let res = [];
 8     for (let i = 0; i < n; i++) {
 9         res.push('a');
10     }
11     k -= n;
12     for (let j = res.length - 1; j >= 0; j--) {
13         res[j] = String.fromCharCode(97 + Math.min(25, k));
14         k -= Math.min(25, k);
15         if (k <= 0) {
16             break;
17         }
18     }
19     return res.join('');
20 };

LeetCode 题目总结