Remove Adjacent Almost-Equal Characters

Med

#2637Time: 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.

Patterns

Dynamic Programming Greedy

Data structures

String

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

string

Walkthrough

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:

State Definition: dp[i][j] = minimum operations for word[0...i] with word[i] being 'a' + j.
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.
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.
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:

1class Solution {2    public int removeAlmostEqualCharacters(String word) {3        int n = word.length();4        // dp[j] will store the min operations for the current prefix ending with 'a'+j5        int[] dp = new int[26];6 7        // Base case: i = 08        for (int j = 0; j < 26; j++) {9            dp[j] = (word.charAt(0) == (char)('a' + j)) ? 0 : 1;10        }11 12        // Fill DP table for i > 013        for (int i = 1; i < n; i++) {14            int[] nextDp = new int[26];15            16            // To optimize finding min(dp[k]) where abs(j-k) > 1, we precompute prefix/suffix mins17            int[] prefixMin = new int[26];18            int[] suffixMin = new int[26];19            prefixMin[0] = dp[0];20            for (int k = 1; k < 26; k++) {21                prefixMin[k] = Math.min(prefixMin[k - 1], dp[k]);22            }23            suffixMin[25] = dp[25];24            for (int k = 24; k >= 0; k--) {25                suffixMin[k] = Math.min(suffixMin[k + 1], dp[k]);26            }27 28            for (int j = 0; j < 26; j++) {29                int cost = (word.charAt(i) == (char)('a' + j)) ? 0 : 1;30                31                int minPrevDp = Integer.MAX_VALUE;32                if (j - 2 >= 0) {33                    minPrevDp = Math.min(minPrevDp, prefixMin[j - 2]);34                }35                if (j + 2 < 26) {36                    minPrevDp = Math.min(minPrevDp, suffixMin[j + 2]);37                }38                39                nextDp[j] = cost + minPrevDp;40            }41            dp = nextDp;42        }43 44        // Find the minimum in the final DP array45        int minOps = Integer.MAX_VALUE;46        for (int val : dp) {47            minOps = Math.min(minOps, val);48        }49 50        return minOps;51    }52}

Complexity

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.

Trade-offs

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.

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.

Algorithm

string

Walkthrough

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:

Initialize an operations counter to 0.
Iterate through the string with an index i from 1 to word.length() - 1.
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.
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.
If the characters are not almost-equal, we simply continue to the next character.
Return the total operations count.

This logic can be implemented concisely in a single loop.

1class Solution {2    public int removeAlmostEqualCharacters(String word) {3        int operations = 0;4        for (int i = 1; i < word.length(); i++) {5            // Check if the current character and the previous one are almost-equal.6            if (Math.abs(word.charAt(i) - word.charAt(i - 1)) <= 1) {7                // If so, we must perform an operation. We choose to change word[i].8                operations++;9                // This single operation can resolve the conflict with word[i-1]10                // and we can pick a character that also avoids conflict with word[i+1].11                // Thus, we can skip checking the next character pair.12                i++;13            }14        }15        return operations;16    }17}

Complexity

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.

Trade-offs

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.

Solutions

Solution

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

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

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem