Medium

题目描述

给你一个字符串 s 和一个整数 k。

定义函数 distance(s1, s2) 计算两个相同长度 n 的字符串 s1 和 s2 之间的距离：

  • 当字符从 'a' 到 'z' 按循环顺序排列时，对于范围 [0, n - 1] 内的所有 i，计算 s1[i] 和 s2[i] 之间的最小距离之和。

例如，distance("ab", "cd") == 4，distance("a", "z") == 1。

你可以将 s 的任何字母更改为任何其他小写英文字母，次数不限。

返回一个字符串，表示经过一些更改后可以得到的字典序最小的字符串 t，使得 distance(s, t) <= k。

示例 1：

输入：s = "zbbz", k = 3
输出："aaaz"
解释：
将 s 更改为 "aaaz"。"zbbz" 和 "aaaz" 之间的距离等于 k = 3。

示例 2：

输入：s = "xaxcd", k = 4
输出："aawcd"
解释：
"xaxcd" 和 "aawcd" 之间的距离等于 k = 4。

示例 3：

输入：s = "lol", k = 0
输出："lol"
解释：
由于 k = 0，无法更改任何字符。

约束：

  • 1 <= s.length <= 100
  • 0 <= k <= 2000
  • s 只包含小写英文字母。

解题思路

这道题需要利用贪心算法来解决。核心思路是从字符串的左端开始，依次尝试将每个字符改成字典序最小的可能字符。

解题思路：

  1. 距离计算：字符间的循环距离为 min(|a-b|, 26-|a-b|)，即顺时针和逆时针的最小值。

  2. 贪心策略：从左到右遍历字符串，对于每个位置：

    • 从字符 ‘a’ 开始尝试，看能否在剩余预算内完成替换
    • 选择第一个满足条件的字符（保证字典序最小）
    • 更新剩余预算

  3. 优化考虑：由于要求字典序最小，我们总是优先尝试更小的字符。如果当前字符已经很小且改变成本较高，可能保持不变更优。

算法步骤：

  • 遍历字符串每个位置
  • 对于位置 i，从 ‘a’ 到 ‘z’ 尝试每个字符
  • 计算替换成该字符需要的代价
  • 如果代价在预算范围内，选择该字符并更新预算
  • 继续处理下一个位置

这种贪心策略能保证得到字典序最小的结果，因为我们总是优先选择更小的字符。

代码实现

class Solution {
public:
    string getSmallestString(string s, int k) {
        string result = s;
        
        for (int i = 0; i < s.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                int distance = min(abs(s[i] - c), 26 - abs(s[i] - c));
                if (distance <= k) {
                    result[i] = c;
                    k -= distance;
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def getSmallestString(self, s: str, k: int) -> str:
        result = list(s)
        
        for i in range(len(s)):
            for c in range(ord('a'), ord('z') + 1):
                char = chr(c)
                distance = min(abs(ord(s[i]) - c), 26 - abs(ord(s[i]) - c))
                if distance <= k:
                    result[i] = char
                    k -= distance
                    break
        
        return ''.join(result)

public class Solution {
    public string GetSmallestString(string s, int k) {
        char[] result = s.ToCharArray();
        
        for (int i = 0; i < s.Length; i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                int distance = Math.Min(Math.Abs(s[i] - c), 26 - Math.Abs(s[i] - c));
                if (distance <= k) {
                    result[i] = c;
                    k -= distance;
                    break;
                }
            }
        }
        
        return new string(result);
    }
}

var getSmallestString = function(s, k) {
    let result = s.split('');
    
    for (let i = 0; i < s.length; i++) {
        for (let c = 97; c <= 122; c++) { // 'a' to 'z'
            let char = String.fromCharCode(c);
            let distance = Math.min(Math.abs(s.charCodeAt(i) - c), 26 - Math.abs(s.charCodeAt(i) - c));
            if (distance <= k) {
                result[i] = char;
                k -= distance;
                break;
            }
        }
    }
    
    return result.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(26n) = O(n)对于每个字符位置，最多尝试26个字符
空间复杂度O(n)需要存储结果字符串

相关题目