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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

小写字符 的 数值 是它在字母表中的位置（从 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。要使得构造出的字符串字典序最小，可以贪心地从字符串左边起始位置开始构造，每次选择一个满足要求的最小字母，即可得到答案。
当然我们每次应尽量选择最小的字母 `a’，但这样可能导致构造出的数值之和小于 n，如何选择每次选择最小的字母才能满足构造的数字之和满足要求，分析如下：

  • 假设我们当前需要构造第 i 个位置的字符 c，此时还剩下 n-i 个位置的字符需要构造，这些字符的数值之和为 k^{‘，剩余的 n-i 个位置的字符最大为 z'，剩余的 n-i 个位置的字符最小为 a’，则此时可以知：
    n - i \le k^{‘} - c \le (n - i) \times 26
    将上述不等式进行转换可得：
    k^{‘} - (n - i) \times 26 \le c \le k - (n - i)

由于 c 最小取值为 1，我们可以得到 c 的合法取值范围为 [\max(1,k^{‘} - (n - i) \times 26), k - (n - i)]，按照贪心原则我们可以取 c 的下限为 \max(1, k^{‘} - (n - i) \times 26)，因此第 i 个字符的最优取值如下:

  • 如果满足 k^{‘} - (n - i) \times 26 \le 0 时，此时选择字符 `a’；
  • 如果满足 k^{‘} - (n - i) \times 26 > 0 时，此时选择数值对应的字符即可。

代码

[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        s = []
        for i in range(1, n + 1):
            lower = max(1, k - (n - i) * 26)
            k -= lower
            s.append(ascii_lowercase[lower - 1])
        return ''.join(s)
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    string getSmallestString(int n, int k) {
        string ans;
        for (int i = 1; i <= n; i++) {
            int lower = max(1, k - (n - i) * 26);
            k -= lower;
            ans.push_back('a' + lower - 1);
        }
        return ans;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public String getSmallestString(int n, int k) {
        StringBuilder ans = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            int lower = Math.max(1, k - (n - i) * 26);
            k -= lower;
            ans.append((char) ('a' + lower - 1));
        }
        return ans.toString();
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public string GetSmallestString(int n, int k) {
        StringBuilder ans = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            int lower = Math.Max(1, k - (n - i) * 26);
            k -= lower;
            ans.Append((char) ('a' + lower - 1));
        }
        return ans.ToString();
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
static inline int max(int a, int b) {
    return a > b ? a : b;
}

char * getSmallestString(int n, int k) {
    char *ans = (char *)malloc(sizeof(char) * (n + 1));
    for (int i = 1; i <= n; i++) {
        int lower = max(1, k - (n - i) * 26);
        k -= lower;
        ans[i - 1] = 'a' + lower - 1;
    }
    ans[n] = '\0';
    return ans;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
var getSmallestString = function(n, k) {
    let ans = '';
    for (let i = 1; i <= n; i++) {
        const lower = Math.max(1, k - (n - i) * 26);
        k -= lower;
        ans += String.fromCharCode('a'.charCodeAt() + lower - 1);
    }
    return ans;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func getSmallestString(n, k int) string {
    s := []byte{}
    for i := 1; i <= n; i++ {
        lower := max(1, k-(n-i)*26)
        k -= lower
        s = append(s, 'a'+byte(lower)-1)
    }
    return string(s)
}

func max(a, b int) int {
    if b > a {
        return b
    }
    return a
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 表示给定的数字 n。我们只需依次构造 n 个字符即可。

  • 空间复杂度：O(1)。除返回值外不需要额外的空间。

 Comments
On this page
1663-具有给定数值的最小字符串