# Remove Adjacent Almost-Equal Characters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-adjacent-almost-equal-characters)
Canonical: https://scaleengineer.com/dsa/problems/remove-adjacent-almost-equal-characters
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** String
---
## 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 _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 "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:**

**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:**

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

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem by building up a solution from smaller subproblems. We define a state `dp[i][char]` representing the minimum operations for the prefix of the string of length `i+1`, ending with a specific character `char`. By iterating through the string and all possible characters, we can compute the optimal solution for the entire string.
**Time:** O(N * C^2), where N is the string length and C is the alphabet size (26). With precomputation of prefix/suffix minimums, this can be optimized to O(N * C). · **Space:** O(N * C) for a naive implementation, where N is the string length and C is the alphabet size (26). This can be optimized to O(C) because each state only depends on the previous state.
**Pros:** Guaranteed to find the optimal solution by exhaustively checking all valid states.; It is a standard and systematic way to solve optimization problems on sequences.
**Cons:** Higher time and space complexity compared to a greedy approach.; The implementation is more complex, involving a 2D array or two arrays for state management.
### Explanation
We can define `dp[i][j]` as the minimum number of operations required for the prefix `word[0...i]` such that the character at index `i` is modified to be the `j`-th letter of the alphabet (`'a' + j`).

**Algorithm:**

1.  **State Definition:** `dp[i][j]` = minimum operations for `word[0...i]` with `word[i]` being `'a' + j`.
2.  **Base Case (i=0):** For the first character, `dp[0][j]` is `1` if `word.charAt(0)` is not `'a' + j` (one change is needed), and `0` otherwise.
3.  **Recurrence Relation (i > 0):** To compute `dp[i][j]`, we consider the cost of changing `word.charAt(i)` to `'a' + j`, and add it to the minimum cost from the previous state `dp[i-1]`. The character at `i-1`, let's say `'a' + k`, must not be almost-equal to `'a' + j`. This means `abs(j - k) > 1`.
    `dp[i][j] = (word.charAt(i) == 'a' + j ? 0 : 1) + min(dp[i-1][k])` for all `k` such that `abs(j - k) > 1`.
4.  **Final Answer:** The result is the minimum value in the last row of our DP table, `min(dp[n-1][j])` for all `j` from 0 to 25.

This can be implemented with a 2D DP table. The complexity can be improved by optimizing the search for `min(dp[i-1][k])` and by reducing the space to `O(C)` since `dp[i]` only depends on `dp[i-1]`.

Here is the space-optimized DP implementation:

```java
class Solution {
    public int removeAlmostEqualCharacters(String word) {
        int n = word.length();
        // dp[j] will store the min operations for the current prefix ending with 'a'+j
        int[] dp = new int[26];

        // Base case: i = 0
        for (int j = 0; j < 26; j++) {
            dp[j] = (word.charAt(0) == (char)('a' + j)) ? 0 : 1;
        }

        // Fill DP table for i > 0
        for (int i = 1; i < n; i++) {
            int[] nextDp = new int[26];
            
            // To optimize finding min(dp[k]) where abs(j-k) > 1, we precompute prefix/suffix mins
            int[] prefixMin = new int[26];
            int[] suffixMin = new int[26];
            prefixMin[0] = dp[0];
            for (int k = 1; k < 26; k++) {
                prefixMin[k] = Math.min(prefixMin[k - 1], dp[k]);
            }
            suffixMin[25] = dp[25];
            for (int k = 24; k >= 0; k--) {
                suffixMin[k] = Math.min(suffixMin[k + 1], dp[k]);
            }

            for (int j = 0; j < 26; j++) {
                int cost = (word.charAt(i) == (char)('a' + j)) ? 0 : 1;
                
                int minPrevDp = Integer.MAX_VALUE;
                if (j - 2 >= 0) {
                    minPrevDp = Math.min(minPrevDp, prefixMin[j - 2]);
                }
                if (j + 2 < 26) {
                    minPrevDp = Math.min(minPrevDp, suffixMin[j + 2]);
                }
                
                nextDp[j] = cost + minPrevDp;
            }
            dp = nextDp;
        }

        // Find the minimum in the final DP array
        int minOps = Integer.MAX_VALUE;
        for (int val : dp) {
            minOps = Math.min(minOps, val);
        }

        return minOps;
    }
}
```
### Algorithm
string

## Greedy Single-Pass Approach
A more efficient approach is to use a greedy strategy. We can iterate through the string once from left to right. Whenever we find a pair of adjacent characters that are almost-equal, we perform an operation to change the second character of the pair. This change effectively resolves the conflict. Since the new character can be chosen to not conflict with the next character, we can skip checking the next position, leading to a simple and fast algorithm.
**Time:** O(N), where N is the length of the string, because we iterate through the string exactly once. · **Space:** O(1), as we only use a few variables to store the index and the operation count.
**Pros:** Highly efficient with a linear time complexity.; Requires only constant extra space.; The implementation is simple and easy to understand.
**Cons:** The correctness of the greedy choice is not immediately obvious and relies on the fact that we can always pick a character for the modification that resolves the current conflict without creating a new one with the next character.
### Explanation
The core idea is to iterate through the string and fix violations as we encounter them. By processing from left to right, we ensure that our decisions don't invalidate previously fixed parts of the string.

**Algorithm:**

1.  Initialize an `operations` counter to 0.
2.  Iterate through the string with an index `i` from 1 to `word.length() - 1`.
3.  At each `i`, check if `word.charAt(i)` and `word.charAt(i-1)` are almost-equal. Two characters `c1` and `c2` are almost-equal if `abs(c1 - c2) <= 1`.
4.  If they are almost-equal, we must perform an operation. The greedy choice is to modify `word[i]`.
    *   Increment the `operations` counter.
    *   By changing `word[i]`, we resolve the conflict with `word[i-1]`. We can always choose a new character for `word[i]` that is not almost-equal to `word[i-1]` and also not almost-equal to `word[i+1]` (since there are at most 6 forbidden characters out of 26). This means the conflict at `(i, i+1)` is also resolved by this single operation.
    *   Therefore, we can skip the check for the next pair by advancing `i` an extra time. The loop's own increment will handle the first step, and we add another `i++` inside the conditional block.
5.  If the characters are not almost-equal, we simply continue to the next character.
6.  Return the total `operations` count.

This logic can be implemented concisely in a single loop.

```java
class Solution {
    public int removeAlmostEqualCharacters(String word) {
        int operations = 0;
        for (int i = 1; i < word.length(); i++) {
            // Check if the current character and the previous one are almost-equal.
            if (Math.abs(word.charAt(i) - word.charAt(i - 1)) <= 1) {
                // If so, we must perform an operation. We choose to change word[i].
                operations++;
                // This single operation can resolve the conflict with word[i-1]
                // and we can pick a character that also avoids conflict with word[i+1].
                // Thus, we can skip checking the next character pair.
                i++;
            }
        }
        return operations;
    }
}
```
### Algorithm
string

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```