Medium

题目描述

给你一个仅由小写英文字母组成的字符串 s。

你可以执行以下操作任意次数（包括零次）：

  • 选择字符串中的任意字符 c，将 c 的每次出现都替换为英文字母表中的下一个字母。

返回将 s 转换为仅由 ‘a’ 字符组成的字符串所需的最少操作次数。

注意：将字母表视为循环的，因此 ‘a’ 在 ‘z’ 之后。

示例 1：

输入：s = "yz"
输出：2
解释：
- 将 'y' 变为 'z' 得到 "zz"。
- 将 'z' 变为 'a' 得到 "aa"。
因此，答案是 2。

示例 2：

输入：s = "a"
输出：0
解释：
字符串 "a" 仅由 'a' 字符组成。因此，答案是 0。

约束条件：

  • 1 <= s.length <= 5 * 10^5
  • s 仅由小写英文字母组成。

解题思路

这道题的关键是理解操作的性质：每次操作会将某个字符的所有出现都向前移动一位。

思路分析：

  1. 单字符分析：对于任意字符 c，要将其变为 ‘a’，需要的操作次数是 (26 - (c - 'a')) % 26。例如 ‘z’ 需要 1 次操作变为 ‘a’，‘y’ 需要 2 次。

  2. 贪心策略：关键洞察是我们可以巧妙地安排操作顺序。当我们操作需要更多步骤的字符时，可能会将其他字符"带动"到目标位置，从而减少总操作次数。

  3. 最优解：通过分析可以发现，最优策略是找出字符串中所有字符到 ‘a’ 的最大距离。这是因为：

    • 我们总是可以先操作距离最远的字符
    • 在操作过程中，其他字符可能会被"顺带"处理
    • 最终的操作次数等于所有字符中到 ‘a’ 距离的最大值

  4. 具体实现：遍历字符串中的所有字符，计算每个字符变为 ‘a’ 需要的步数，取最大值即为答案。

代码实现

class Solution {
public:
    int minOperations(string s) {
        int maxOps = 0;
        for (char c : s) {
            int ops = (26 - (c - 'a')) % 26;
            maxOps = max(maxOps, ops);
        }
        return maxOps;
    }
};

class Solution:
    def minOperations(self, s: str) -> int:
        max_ops = 0
        for c in s:
            ops = (26 - (ord(c) - ord('a'))) % 26
            max_ops = max(max_ops, ops)
        return max_ops

public class Solution {
    public int MinOperations(string s) {
        int maxOps = 0;
        foreach (char c in s) {
            int ops = (26 - (c - 'a')) % 26;
            maxOps = Math.Max(maxOps, ops);
        }
        return maxOps;
    }
}

var minOperations = function(s) {
    let maxOps = 0;
    for (let c of s) {
        let ops = (26 - (c.charCodeAt(0) - 'a'.charCodeAt(0))) % 26;
        maxOps = Math.max(maxOps, ops);
    }
    return maxOps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)需要遍历字符串中的每个字符一次
空间复杂度O(1)只使用了常量级的额外空间