Medium

题目描述

给你一个下标从 0 开始的字符串 word。

在一次操作中，你可以选择 word 的任意下标 i，并将 word[i] 改为任意小写英文字母。

返回使 word 不含相邻几乎相等字符所需的 最少 操作数。

如果 a == b 或者 a 和 b 在字母表中相邻，则认为两个字符 a 和 b 几乎相等。

示例 1：

输入：word = "aaaaa"
输出：2
解释：我们可以将 word 改为 "acaca"，它不包含相邻的几乎相等字符。
可以证明，移除 word 中所有相邻几乎相等字符所需的最少操作数是 2。

示例 2：

输入：word = "abddez"
输出：2
解释：我们可以将 word 改为 "ybdoez"，它不包含相邻的几乎相等字符。
可以证明，移除 word 中所有相邻几乎相等字符所需的最少操作数是 2。

示例 3：

输入：word = "zyxyxyz"
输出：3
解释：我们可以将 word 改为 "zaxaxaz"，它不包含相邻的几乎相等字符。
可以证明，移除 word 中所有相邻几乎相等字符所需的最少操作数是 3。

提示：

  • 1 <= word.length <= 100
  • word 只包含小写英文字母

解题思路

这个问题的核心思路是使用贪心算法从左到右扫描字符串。

首先理解"几乎相等"的定义：两个字符相等或者在字母表中相邻（如 ‘a’和’b’、‘b’和’c’等）。

贪心策略： 当我们发现当前位置 i 的字符与前一个位置 i-1 的字符几乎相等时，我们必须修改其中一个。为了最优解，我们选择修改当前位置 i 的字符，因为：

  1. 修改当前字符不会影响已经处理过的前面部分
  2. 我们可以选择一个既不与 word[i-1] 几乎相等，也不与 word[i+1]（如果存在）几乎相等的字符

由于英文字母有26个，而每个字符最多与4个字符几乎相等（自身、前一个、后一个，以及可能重复的），所以总能找到合适的替换字符。

算法步骤：

  1. 从左到右遍历字符串
  2. 检查当前字符是否与前一个字符几乎相等
  3. 如果是，计数器加1（表示需要修改当前字符）
  4. 继续处理下一个字符

这种贪心方法保证了最少的操作次数，因为我们每次遇到冲突时都立即解决，避免了后续的连锁反应。

代码实现

class Solution {
public:
    int removeAlmostEqualCharacters(string word) {
        int operations = 0;
        
        for (int i = 1; i < word.length(); i++) {
            if (isAlmostEqual(word[i], word[i-1])) {
                operations++;
                // 贪心：跳过下一个字符的检查，因为我们已经"修改"了当前字符
                i++;
            }
        }
        
        return operations;
    }
    
private:
    bool isAlmostEqual(char a, char b) {
        return a == b || abs(a - b) == 1;
    }
};

class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        operations = 0
        i = 1
        
        while i < len(word):
            if self.is_almost_equal(word[i], word[i-1]):
                operations += 1
                # 贪心：跳过下一个字符的检查，因为我们已经"修改"了当前字符
                i += 2
            else:
                i += 1
        
        return operations
    
    def is_almost_equal(self, a: str, b: str) -> bool:
        return a == b or abs(ord(a) - ord(b)) == 1

public class Solution {
    public int RemoveAlmostEqualCharacters(string word) {
        int operations = 0;
        
        for (int i = 1; i < word.Length; i++) {
            if (IsAlmostEqual(word[i], word[i-1])) {
                operations++;
                // 贪心：跳过下一个字符的检查，因为我们已经"修改"了当前字符
                i++;
            }
        }
        
        return operations;
    }
    
    private bool IsAlmostEqual(char a, char b) {
        return a == b || Math.Abs(a - b) == 1;
    }
}

var removeAlmostEqualCharacters = function(word) {
    function areAlmostEqual(a, b) {
        return a === b || Math.abs(a.charCodeAt(0) - b.charCodeAt(0)) === 1;
    }
    
    let operations = 0;
    let i = 0;
    
    while (i < word.length - 1) {
        if (areAlmostEqual(word[i], word[i + 1])) {
            operations++;
            i += 2;
        } else {
            i++;
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。我们只需要遍历一次字符串，每次操作都是常数时间，因此时间复杂度为 O(n)。算法只使用了常数额外空间来存储操作计数和循环变量。

相关题目