Welcome to Subscribe On Youtube
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)$.

class Solution { public int removeAlmostEqualCharacters(String word) { int ans = 0, n = word.length(); for (int i = 1; i < n; ++i) { if (Math.abs(word.charAt(i)  word.charAt(i  1)) < 2) { ++ans; ++i; } } return ans; } }

class Solution { public: int removeAlmostEqualCharacters(string word) { int ans = 0, n = word.size(); for (int i = 1; i < n; ++i) { if (abs(word[i]  word[i  1]) < 2) { ++ans; ++i; } } return ans; } };

class Solution: def removeAlmostEqualCharacters(self, word: str) > int: ans = 0 i, n = 1, len(word) while i < n: if abs(ord(word[i])  ord(word[i  1])) < 2: ans += 1 i += 2 else: i += 1 return ans

func removeAlmostEqualCharacters(word string) (ans int) { for i := 1; i < len(word); i++ { if abs(int(word[i])int(word[i1])) < 2 { ans++ i++ } } return } func abs(x int) int { if x < 0 { return x } return x }

function removeAlmostEqualCharacters(word: string): number { let ans = 0; for (let i = 1; i < word.length; ++i) { if (Math.abs(word.charCodeAt(i)  word.charCodeAt(i  1)) < 2) { ++ans; ++i; } } return ans; }