2957. Remove Adjacent AlmostEqual Characters
Description
You are given a 0indexed 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 almostequal characters from word
.
Two characters a
and b
are almostequal 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 almostequal characters. It can be shown that the minimum number of operations needed to remove all adjacent almostequal 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 almostequal characters. It can be shown that the minimum number of operations needed to remove all adjacent almostequal 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 almostequal characters. It can be shown that the minimum number of operations needed to remove all adjacent almostequal characters from word is 3.
Constraints:
1 <= word.length <= 100
word
consists only of lowercase English letters.
Solutions
Solution 1: Greedy
We start traversing the string word
from index $1$. If word[i]
and word[i  1]
are approximately equal, we greedily replace word[i]
with a character that is not equal to both word[i  1]
and word[i + 1]
(we can choose not to perform the replacement operation, just record the number of operations). Then, we skip word[i + 1]
and continue to traverse the string word
.
Finally, we return the recorded number of operations.
The time complexity is $O(n)$, where $n$ is the length of the string word
. The space complexity is $O(1)$.









