消除相邻近似相等字符

难度: 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 只包含小写英文字母。

Submission

运行时间: 27 ms

内存: 16.1 MB

class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        ans = 0
        start = 1
        wl = len(word)

        while start < wl:
            if abs(ord(word[start -1]) - ord(word[start])) <= 1:
                ans = ans + 1
                start = start + 2
            else:
                start = start + 1
        return ans

Explain

此题解的思路基于贪心算法，目的是通过最少的修改次数去除字符串中所有相邻的近似相等字符。定义两个字符为近似相等，如果它们是相同的或者在英文字母表中相邻。解决方案从字符串的第二个字符开始遍历，比较每个字符与它前一个字符的ASCII码差的绝对值。如果这个差的绝对值小于等于1，说明这两个字符是近似相等的，需要将其中一个字符修改为一个不同且不相邻的字符，然后跳过下一个字符（因为已经修改了当前字符，所以跳过下一个字符以避免重复处理）。如果不是近似相等，则继续检查下一对字符。通过这种方式，逐对检查并修改字符，直到字符串末尾。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        ans = 0  # 初始化操作次数为0
        start = 1  # 从第二个字符开始检查
        wl = len(word)  # 字符串长度

        while start < wl:  # 遍历字符串
            # 检查当前字符与前一个字符是否近似相等
            if abs(ord(word[start -1]) - ord(word[start])) <= 1:
                ans = ans + 1  # 是近似相等字符，增加操作次数
                start = start + 2  # 跳过下一个字符
            else:
                start = start + 1  # 检查下一对字符
        return ans  # 返回最小操作次数

Explore

在贪心算法中，跳过下一个字符是基于一个假设：当修改一个字符以消除其与前一个字符的近似相等关系时，该字符与后一个字符之间不会形成新的近似相等关系。这种处理方式简化了问题，减少了修改次数。然而，这个假设不总是正确，确实存在因跳过而错过需要修改的相邻字符对的情况。这可能导致算法没有达到理想的最优解，但仍然可以提供一个近似解。在实际应用中，这种方法的效率和实现的简单性是其主要优点。

选择一个合适的替换字符时，应避免选择与当前字符相同或相邻的字符，同时也需要考虑新字符不会与前一个或后一个字符形成新的近似相等关系。理想情况下，可以选择字母表中离当前字符最远的字符，例如将 'a' 或 'b' 替换为 'z'，或相反。这样的选择可以最大程度地减少后续可能需要的修改次数。然而，选择最佳替换字符可能需要根据上下文动态决定，以适应不同的输入字符串。

在ASCII码表中，相邻的英文字母（如 'a' 和 'b'，'b' 和 'c'）的ASCII码值相差确实为1。然而，对于非字母字符或大小写不同的英文字母（如 'a' 和 'A'），ASCII码差值可能为1或更小，但它们并非相邻字母。因此，如果字符串包含大小写字母或非字母字符，仅使用ASCII码差来判断可能不准确。应考虑扩展判断逻辑，仅对小写或大写英文字母应用ASCII差值判断。

代码实现假设一旦发现近似相等的字符对，就必须修改其中一个字符，并跳过下一个字符。这种方法虽然简单，但并非总是最优。在某些情况下，可能存在不需要修改的字符对，或者通过修改不同的字符可以达到更少的总修改次数。一个更优的方法可能包括更复杂的逻辑，如动态规划，考虑多个字符的相互关系，以寻求全局最小的修改次数。然而，这将增加实现的复杂性。