2957. Remove Adjacent Almost-Equal Characters
Description
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.
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)$.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 |
|