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.
Iterate through the string and for each pair of adjacent characters, check if they are almost-equal. If they are, change one of them optimally to ensure no such pairs remain. This approach works by making a local decision at each step that looks globally optimal.
The solution iterates over each character in the string. If it finds two adjacent characters that are almost-equal, it modifies the latter character to break the almost-equal state. This modification is done by shifting the character within the alphabet. This greedy approach ensures minimal operations as each modification breaks the local almost-equal consecutiveness.
Time Complexity: O(n), where n is the length of the string. This results from the single pass through the string.
Space Complexity: O(1), in-place operations are conducted without additional space.
In this approach, utilize dynamic programming to calculate the minimum operations. Construct a DP array where dp[i] denotes the minimum number of operations required to make the string up to index i free of almost-equal adjacent characters. Leverage previously computed values for optimizing current decisions.
In C, a dynamic array 'dp' is utilized to keep track of the minimum number of changes required at each stage of the array. This considers the fact that changing a character might affect future characters in the process.
Time Complexity: O(n), single pass computation.
Space Complexity: O(n), owing to the additional dp array used.
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).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), where n is the length of the string. This results from the single pass through the string. |
| Dynamic Programming Approach | Time Complexity: O(n), single pass computation. |
| Greedy | — |
| 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. |
leetcode Biweekly Contest 119 solution | Remove Adjacent Almost-Equal Characters| ALL SOLUTION • CODES WAR • 1,281 views views
Watch 8 more video solutions →Practice Remove Adjacent Almost-Equal Characters with our built-in code editor and test cases.
Practice on FleetCode