Watch 9 video solutions for Remove Adjacent Almost-Equal Characters, a medium level problem involving String, Dynamic Programming, Greedy. This walkthrough by CODES WAR has 1,281 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 100word consists only of lowercase English letters.Problem Overview: You receive a lowercase string s. Two characters are almost equal if their ASCII difference is at most 1 (for example 'a' and 'b', or 'c' and 'c'). The goal is to remove the minimum number of characters so that no two adjacent characters in the final string are almost equal.
Approach 1: Greedy Scan (O(n) time, O(1) space)
The key observation: if s[i] and s[i+1] are almost equal, at least one of them must be removed. Instead of exploring both possibilities, pair them immediately and count one deletion. During a left‑to‑right scan, whenever abs(s[i] - s[i+1]) <= 1, increment the removal counter and skip the next index because the conflicting pair has been handled. If the characters are not almost equal, simply move to the next character. This greedy pairing works because keeping both characters can never lead to a valid sequence, so resolving the conflict locally is always optimal. The algorithm only performs a single pass through the string, giving linear time and constant memory.
Approach 2: Dynamic Programming (O(n) time, O(n) space)
A dynamic programming formulation models the decision of whether to keep or remove characters while preserving the constraint with the previously kept character. Define dp[i] as the minimum removals needed considering the prefix ending at index i. When processing s[i], compare it with the last kept character. If they are almost equal, you must remove either the current character or the previous one, so the state transitions consider both possibilities and take the minimum. If they are not almost equal, you safely extend the sequence without extra deletions. This approach explicitly captures all valid states and guarantees correctness, though it uses extra memory compared with the greedy scan.
The greedy solution is effectively a simplified form of the DP reasoning. Since every adjacent conflict is independent of future characters, resolving it immediately yields the same optimal result with far less overhead.
Recommended for interviews: Start by explaining the greedy observation: whenever two neighbors differ by at most 1, one must be removed. Implement a single pass with index skipping to avoid overlapping pairs. This demonstrates clear reasoning about greedy algorithms and achieves the optimal O(n) runtime with O(1) space. Mentioning the DP formulation shows deeper understanding, but interviewers typically expect the greedy implementation.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Scan | O(n) | O(1) | Best general solution. Single pass and constant memory. |
| Dynamic Programming | O(n) | O(n) | Useful for explaining state transitions or extending the problem with more constraints. |