Problem

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 theminimum 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.

Examples

Example 1

1
2
3
4

Input: word = "aaaaa"
Output: 2
Explanation: We can change word into "a** _c_** a _**c**_ a" 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

1
2
3
4

Input: word = "abddez"
Output: 2
Explanation: We can change word into "**_y_** bd _**o**_ ez" 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

1
2
3
4

Input: word = "zyxyxyz"
Output: 3
Explanation: We can change word into "z _**a**_ x _**a**_ x** _a_** z" 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.

Solution

Method 1 – Greedy Linear Scan

Intuition

If two adjacent characters are almost-equal (same or consecutive in the alphabet), we must change one of them. The optimal way is to change every second character in such a pair, and skip the next character to avoid double-counting overlapping pairs.

Approach

  1. Initialize a counter for operations.
  2. Iterate through the string from left to right.
  3. For each index, check if the current and next character are almost-equal (same or differ by 1 in ASCII).
  4. If so, increment the counter and skip the next character (move i by 2), else move to the next character (i by 1).
  5. Return the counter.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
public:
    int removeAlmostEqualCharacters(string word) {
        int ans = 0, n = word.size();
        for (int i = 0; i < n - 1;) {
            if (word[i] == word[i+1] || abs(word[i] - word[i+1]) == 1) {
                ++ans;
                i += 2;
            } else {
                ++i;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func removeAlmostEqualCharacters(word string) int {
    ans, n := 0, len(word)
    for i := 0; i < n-1; {
        if word[i] == word[i+1] || abs(int(word[i])-int(word[i+1])) == 1 {
            ans++
            i += 2
        } else {
            i++
        }
    }
    return ans
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    public int removeAlmostEqualCharacters(String word) {
        int ans = 0, n = word.length();
        for (int i = 0; i < n - 1;) {
            if (word.charAt(i) == word.charAt(i+1) || Math.abs(word.charAt(i) - word.charAt(i+1)) == 1) {
                ans++;
                i += 2;
            } else {
                i++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun removeAlmostEqualCharacters(word: String): Int {
        var ans = 0
        var i = 0
        while (i < word.length - 1) {
            if (word[i] == word[i+1] || kotlin.math.abs(word[i] - word[i+1]) == 1) {
                ans++
                i += 2
            } else {
                i++
            }
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def removeAlmostEqualCharacters(self, word: str) -> int:
        ans = 0
        i = 0
        n = len(word)
        while i < n - 1:
            if word[i] == word[i+1] or abs(ord(word[i]) - ord(word[i+1])) == 1:
                ans += 1
                i += 2
            else:
                i += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn remove_almost_equal_characters(word: String) -> i32 {
        let bytes = word.as_bytes();
        let mut ans = 0;
        let mut i = 0;
        while i + 1 < bytes.len() {
            if bytes[i] == bytes[i+1] || (bytes[i] as i32 - bytes[i+1] as i32).abs() == 1 {
                ans += 1;
                i += 2;
            } else {
                i += 1;
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    removeAlmostEqualCharacters(word: string): number {
        let ans = 0, i = 0, n = word.length;
        while (i < n - 1) {
            if (word[i] === word[i+1] || Math.abs(word.charCodeAt(i) - word.charCodeAt(i+1)) === 1) {
                ans++;
                i += 2;
            } else {
                i++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string, since we scan the string once.
  • 🧺 Space complexity: O(1), as only a few variables are used.