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.In #2957 Remove Adjacent Almost-Equal Characters, the goal is to ensure that no two adjacent characters in the string are almost equal (their ASCII difference is less than or equal to 1). The task is to determine the minimum number of operations required to modify characters so that this condition is avoided.
A common way to approach this problem is using a greedy scan. Traverse the string from left to right and check each pair of adjacent characters. If abs(s[i] - s[i+1]) <= 1, the pair violates the rule. In such cases, perform an operation to modify one of the characters and skip the next index, since the modification effectively resolves that pair.
This strategy works because resolving the earliest conflicting pair prevents cascading conflicts later. While the problem can also be reasoned about using dynamic programming for state transitions, the greedy approach achieves the optimal result with simpler logic. The overall complexity is O(n) time with O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy Linear Scan | O(n) | O(1) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
For <code>i > 0</code>, if <code>word[i]</code> and <code>word[i - 1]</code> are adjacent, we will change <code>word[i]</code> to another character. Which character should we change it to?
We will change <code>word[i]</code> to some character that is not adjacent to <code>word[i - 1]</code> nor <code>word[i + 1]</code> (if it exists). Such a character always exists. However, since the problem does not ask for the final state of the string, It is enough to prove that the character exists and we do not need to find it.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Problems like this are common in coding interviews because they test string manipulation, greedy reasoning, and edge-case handling. Variations of adjacent constraint problems frequently appear in interviews at major tech companies.
No complex data structure is required for this problem. A simple string traversal with index pointers is sufficient since the decision only depends on adjacent character comparisons.
The optimal approach uses a greedy linear scan. While iterating through the string, check each adjacent pair and count an operation whenever their character difference is less than or equal to one. After resolving such a pair, skip the next index to avoid overlapping conflicts.
Yes, a dynamic programming perspective can model choices for modifying characters and avoiding conflicts. However, the greedy strategy works because fixing the earliest invalid pair never harms future decisions, making DP unnecessary for optimal performance.