消除相邻近似相等字符

You are given a 0-indexed string word.

In one operation, you can pick any index i of word and change word[i] to any lowercase English letter.

Return the minimum number of operations needed to remove all adjacent almost-equal characters from word.

Two characters a and b are almost-equal if a == b or a and b are adjacent in the alphabet.

 

Example 1:

Input: word = "aaaaa"
Output: 2
Explanation: We can change word into "acaca" which does not have any adjacent almost-equal characters.
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 2.

Example 2:

Input: word = "abddez"
Output: 2
Explanation: We can change word into "ybdoez" which does not have any adjacent almost-equal characters.
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 2.

Example 3:

Input: word = "zyxyxyz"
Output: 3
Explanation: We can change word into "zaxaxaz" which does not have any adjacent almost-equal characters. 
It can be shown that the minimum number of operations needed to remove all adjacent almost-equal characters from word is 3.

 

Constraints:

• 1 <= word.length <= 100
• word consists only of lowercase English letters.

/*
题目思路：
1. 使用Java Stream遍历字符串中的字符。
2. 利用Stream的特性进行过滤和映射，将近似相等的字符修改。
3. 计算并返回最小操作次数。
*/

import java.util.stream.IntStream;

public class Solution {
    public int minOperations(String word) {
        int[] operations = {0};
        StringBuilder sb = new StringBuilder(word);
        IntStream.range(0, word.length() - 1)
                .forEach(i -> {
                    if (areSimilar(sb.charAt(i), sb.charAt(i + 1))) {
                        operations[0]++;
                        sb.setCharAt(i + 1, getReplacementChar(sb.charAt(i), sb.charAt(i + 1)));
                    }
                });
        return operations[0];
    }

    private boolean areSimilar(char a, char b) {
        return a == b || Math.abs(a - b) == 1;
    }

    private char getReplacementChar(char a, char b) {
        return IntStream.range('a', 'z' + 1)
                .filter(c -> c != a && c != b && Math.abs(c - a) > 1 && Math.abs(c - b) > 1)
                .mapToObj(c -> (char) c)
                .findFirst().orElse('a');
    }
}

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

O(n)

O(1)