Medium

题目描述

小写字符的数值定义为它在字母表中的位置（从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 数值为 27 的字典序最小的字符串。

示例 2：

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

提示：

  • 1 <= n <= 10^5
  • n <= k <= 26 * n

解题思路

这道题需要构造一个长度为 n、数值和为 k 的字典序最小的字符串。

核心思路：贪心算法

要使字典序最小，我们应该让前面的字符尽可能小。但同时要保证剩余位置能够填满剩余的数值。

贪心策略：

  1. 从左到右遍历每个位置
  2. 对于当前位置，尝试放置尽可能小的字符
  3. 但要确保剩余位置（每个位置最大值为26，即’z’）能够覆盖剩余的数值

具体算法：

  • 对于第 i 个位置（0-indexed），剩余位置数为 n-1-i
  • 剩余最大可能数值为 (n-1-i) * 26
  • 当前位置最小可放置的字符值为 max(1, k - 剩余最大可能数值)
  • 放置该字符后，更新 k 值

这种方法保证了每个位置都放置了在满足约束条件下尽可能小的字符，从而得到字典序最小的结果。

时间复杂度为 O(n)，空间复杂度为 O(n)（用于存储结果字符串）。

代码实现

class Solution {
public:
    string getSmallestString(int n, int k) {
        string result(n, 'a');
        k -= n; // 减去所有位置放'a'的基础值
        
        // 从后往前填充，尽可能放大的字符
        for (int i = n - 1; i >= 0 && k > 0; i--) {
            int add = min(k, 25); // 最多能增加25（从'a'到'z'）
            result[i] = 'a' + add;
            k -= add;
        }
        
        return result;
    }
};

class Solution:
    def getSmallestString(self, n: int, k: int) -> str:
        result = ['a'] * n
        k -= n  # 减去所有位置放'a'的基础值
        
        # 从后往前填充，尽可能放大的字符
        i = n - 1
        while i >= 0 and k > 0:
            add = min(k, 25)  # 最多能增加25（从'a'到'z'）
            result[i] = chr(ord('a') + add)
            k -= add
            i -= 1
        
        return ''.join(result)

public class Solution {
    public string GetSmallestString(int n, int k) {
        char[] result = new char[n];
        Array.Fill(result, 'a');
        k -= n; // 减去所有位置放'a'的基础值
        
        // 从后往前填充，尽可能放大的字符
        for (int i = n - 1; i >= 0 && k > 0; i--) {
            int add = Math.Min(k, 25); // 最多能增加25（从'a'到'z'）
            result[i] = (char)('a' + add);
            k -= add;
        }
        
        return new string(result);
    }
}

var getSmallestString = function(n, k) {
    let result = new Array(n).fill('a');
    k -= n; // 减去所有位置放'a'的基础值
    
    // 从后往前填充，尽可能放大的字符
    for (let i = n - 1; i >= 0 && k > 0; i--) {
        let add = Math.min(k, 25); // 最多能增加25（从'a'到'z'）
        result[i] = String.fromCharCode('a'.charCodeAt(0) + add);
        k -= add;
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(n)
  • 时间复杂度：O(n)，需要遍历字符串的每个位置一次
  • 空间复杂度：O(n)，需要存储长度为 n 的结果字符串