原文链接: https://leetcode-cn.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 <= 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] 靠前。

 

示例 1：

输入：n = 3, k = 27
输出："aay"
解释：字符串的数值为 1 + 1 + 25 = 27，它是数值满足要求且长度等于 3 字典序最小的字符串。

示例 2：

输入：n = 5, k = 73
输出："aaszz"

 

提示：

• 1 <= n <= 105
• n <= k <= 26 * n

通过代码

高赞题解

方法一：贪心算法

思路与算法

由于我们要使得构造出的字符串字典序最小，因此可以考虑贪心地从字符串的开头处开始构造，每次选择一个满足要求的最小的字母，即可得到最终答案。

那么怎样选择字母才是满足要求的呢？假设我们当前构造到了某一个位置，包括此位置还剩下 $n’$ 个位置没有放入字符，并且这些位置的数值之和为 $k’$，那么如果我们放入字母 $c$，那么剩余 $n’-1$ 个位置以及 $k’-c$ 的数值之和，必须满足：

$$
n’-1 \leq k’-c \leq 26(n’-1)
$$

即：

$$
k’-26(n’-1) \leq c \leq k’-(n’-1)
$$

那么我们就得到了 $c$ 的取值下限 $k’-26(n’-1)$。因此：

• 如果 $k’-26(n’-1) \leq 0$，我们选择字符 $\texttt{a}$；

• 如果 $k’-26(n’-1) > 0$，我们选择该数值对应的字符。

代码

[sol1-C++]
class Solution {
public:
    string getSmallestString(int n, int k) {
        string ans;
        for (int rest = n; rest >= 1; --rest) {
            int bound = k - 26 * (rest - 1);
            if (bound > 0) {
                ans += char(bound + 'a' - 1);
                k -= bound;
            }
            else {
                ans += 'a';
                k -= 1;
            }
        }
        return ans;
    }
};

[sol1-Python3]
class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        ans = list()
        for rest in range(n, 0, -1):
            bound = k - 26 * (rest - 1)
            if bound > 0:
                ans.append(chr(bound + 96))
                k -= bound
            else:
                ans.append("a")
                k -= 1
        return "".join(ans)

复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度：$O(1)$。

统计信息

通过次数	提交次数	AC比率
7918	13840	57.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言