Remove Adjacent Almost-Equal Characters solution and explanation
8 more videos on this problem
leetcode Biweekly Contest 119 solution | Remove Adjacent Almost-Equal Characters| ALL SOLUTIONCODES WAR · 1:31 · 1K views
2957. Remove Adjacent Almost-Equal Characters || Greedy 🔥Ayush Rao · 6:06 · 508 views
2957. Remove Adjacent Almost-Equal Characters | LEETCODE BIWEEKLY 119 | GREEDYcode Explainer · 7:22 · 306 views
2957. Remove Adjacent Almost-Equal Characters (Leetcode Medium)Programming Live with Larry · 10:54 · 219 views
Leetcode 2957. Remove Adjacent Almost-Equal CharactersElite Code · 20:31 · 167 views
Remove Adjacent Almost-Equal Characters | Leetcode Biweekly contest 119 | DCC NIT-ADCC NITA · 3:38 · 117 views
Remove Adjacent Almost-Equal Characters - LeetCode 2957 - PythonAlpha-Code · 14:28 · 99 views
Remove Adjacent Almost-Equal Characters || Biweekly Contest || LeetcodecodeSolution · 11:10 · 66 views
biweely 119 | remove adjacent almost equal characters | contest | leetcodeHelping hands by Sumit · 0:15 · 65 views
The 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 "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 <= 100wordconsists only of lowercase English letters.
Approach overview
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 1: Greedy Approach
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.
def min_operations(word):
operations = 0
word = list(word)
for i in range(len(word) - 1):
if word[i] == word[i+1] or abs(ord(word[i]) - ord(word[i+1])) == 1:
word[i+1] = 'a' if word[i+1] == 'z' else chr(ord(word[i+1]) + 1)
operations += 1
return operations
print(min_operations('zyxyxyz'))public class Solution {
public int minOperations(String word) {
int operations = 0;
char[] chars = word.toCharArray();
for (int i = 0; i < chars.length - 1; i++) {
if (chars[i] == chars[i+1] || Math.abs(chars[i] - chars[i+1]) == 1) {
chars[i+1] = (char) ((chars[i+1] == 'z') ? 'a' : chars[i+1] + 1);
operations++;
}
}
return operations;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minOperations("zyxyxyz"));
}
}#include <iostream>
#include <string>
using namespace std;
int min_operations(string word) {
int operations = 0;
for (size_t i = 0; i < word.size() - 1; ++i) {
if (word[i] == word[i+1] || abs(word[i] - word[i+1]) == 1) {
word[i+1] = (word[i+1] == 'z') ? 'a' : word[i+1] + 1;
++operations;
}
}
return operations;
}
int main() {
string word = "zyxyxyz";
cout << min_operations(word) << endl;
return 0;
}function minOperations(word) {
let operations = 0;
let chars = word.split('');
for (let i = 0; i < chars.length - 1; i++) {
if (chars[i] === chars[i+1] || Math.abs(chars[i].charCodeAt(0) - chars[i+1].charCodeAt(0)) === 1) {
chars[i+1] = chars[i+1] === 'z' ? 'a' : String.fromCharCode(chars[i+1].charCodeAt(0) + 1);
operations++;
}
}
return operations;
}
console.log(minOperations('zyxyxyz'));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int min_operations(char* word) {
int operations = 0;
int length = strlen(word);
for (int i = 0; i < length - 1; i++) {
if (word[i] == word[i+1] || abs(word[i] - word[i+1]) == 1) {
word[i+1] = word[i+1] == 'z' ? 'a' : word[i+1] + 1;
operations++;
}
}
return operations;
}
int main() {
char word[] = "zyxyxyz";
printf("%d\n", min_operations(word));
return 0;
}using System;
public class Solution {
public int MinOperations(string word) {
int operations = 0;
char[] charArray = word.ToCharArray();
for (int i = 0; i < charArray.Length - 1; i++) {
if (charArray[i] == charArray[i+1] || Math.Abs(charArray[i] - charArray[i+1]) == 1) {
charArray[i+1] = charArray[i+1] == 'z' ? 'a' : (char)(charArray[i+1] + 1);
operations++;
}
}
return operations;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinOperations("zyxyxyz"));
}
}By converting the string into a list, Python allows mutable iteration and condition-based alteration of adjacent characters. Each cycle verifies adjacent pairs and updates the next character if required, reducing the pair's status.
Time Complexity: O(n), dictated by the input’s length.
Space Complexity: O(1), involves mutable string operations.
Approach 2: Dynamic Programming Approach
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.
def min_operations(word):
n = len(word)
dp = [0] * n
word = list(word)
for i in range(1, n):
dp[i] = dp[i - 1]
if word[i] == word[i - 1] or abs(ord(word[i]) - ord(word[i - 1])) == 1:
dp[i] += 1
word[i] = 'a' if word[i] == 'z' else chr(ord(word[i]) + 1)
return dp[-1]
print(min_operations('zyxyxyz'))public class Solution {
public int minOperations(String word) {
int n = word.length();
int[] dp = new int[n];
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1];
if (word.charAt(i) == word.charAt(i-1) || Math.abs(word.charAt(i) - word.charAt(i-1)) == 1) {
dp[i]++;
word = word.substring(0, i) + (char)((word.charAt(i) == 'z') ? 'a' : word.charAt(i) + 1) + word.substring(i + 1);
}
}
return dp[n - 1];
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minOperations("zyxyxyz"));
}
}#include <iostream>
#include <vector>
#include <string>
using namespace std;
int min_operations(string word) {
int n = word.size();
vector<int> dp(n, 0);
for (int i = 1; i < n; ++i) {
dp[i] = dp[i - 1];
if (word[i] == word[i-1] || abs(word[i] - word[i-1]) == 1) {
dp[i]++;
word[i] = (word[i] == 'z') ? 'a' : (word[i] + 1);
}
}
return dp[n - 1];
}
int main() {
string word = "zyxyxyz";
cout << min_operations(word) << endl;
return 0;
}function minOperations(word) {
let n = word.length;
let dp = new Array(n).fill(0);
let chars = word.split('');
for (let i = 1; i < n; i++) {
dp[i] = dp[i - 1];
if (chars[i] === chars[i-1] || Math.abs(chars[i].charCodeAt(0) - chars[i-1].charCodeAt(0)) === 1) {
dp[i]++;
chars[i] = chars[i] === 'z' ? 'a' : String.fromCharCode(chars[i].charCodeAt(0) + 1);
}
}
return dp[n - 1];
}
console.log(minOperations('zyxyxyz'));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int min_operations(char* word) {
int n = strlen(word);
int *dp = (int*)malloc(n * sizeof(int));
dp[0] = 0;
for (int i = 1; i < n; ++i) {
dp[i] = dp[i - 1];
if (word[i] == word[i-1] || abs(word[i] - word[i-1]) == 1) {
dp[i]++;
word[i] = (word[i] == 'z') ? 'a' : (word[i] + 1);
}
}
int operations = dp[n - 1];
free(dp);
return operations;
}
int main() {
char word[] = "zyxyxyz";
printf("%d\n", min_operations(word));
return 0;
}using System;
public class Solution {
public int MinOperations(string word) {
int n = word.Length;
int[] dp = new int[n];
char[] charArray = word.ToCharArray();
for (int i = 1; i < n; i++) {
dp[i] = dp[i - 1];
if (charArray[i] == charArray[i - 1] || Math.Abs(charArray[i] - charArray[i - 1]) == 1) {
dp[i]++;
charArray[i] = charArray[i] == 'z' ? 'a' : (char)(charArray[i] + 1);
}
}
return dp[n - 1];
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinOperations("zyxyxyz"));
}
}Python employs lists to form the DP array, utilizing dynamic checks and updates of character sequences during iteration to minimize adjacent almost-equal characters.
Time Complexity: O(n), facilitated through consistent traversal.
Space Complexity: O(n), as a consequence of the dp array.
Approach 3: Greedy
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).
function removeAlmostEqualCharacters(word: string): number {
let ans = 0;
for (let i = 1; i < word.length; ++i) {
if (Math.abs(word.charCodeAt(i) - word.charCodeAt(i - 1)) < 2) {
++ans;
++i;
}
}
return ans;
}func removeAlmostEqualCharacters(word string) (ans int) {
for i := 1; i < len(word); i++ {
if abs(int(word[i])-int(word[i-1])) < 2 {
ans++
i++
}
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach | Time Complexity: O(n), dictated by the input’s length. |
| Dynamic Programming Approach | Time Complexity: O(n), facilitated through consistent traversal. |
| Greedy | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Remove Adjacent Almost-Equal Characters easy or hard?
The problem is rated Medium on LeetCode with an acceptance rate around 53%. The logic becomes straightforward after recognizing the greedy pairing insight, but identifying that local conflicts can be resolved independently is the key step.
Remove Adjacent Almost-Equal Characters Python/Java solution
Most implementations follow the same greedy pattern across languages. Iterate through the string, check if abs(s[i] - s[i+1]) ≤ 1, increment a counter, and skip the next index when a conflict appears. The logic translates directly to Python, Java, C++, C#, and JavaScript.
How to solve Remove Adjacent Almost-Equal Characters in O(n)?
Perform a single linear scan. For each pair of neighbors s[i] and s[i+1], compute abs(s[i] - s[i+1]). If the value is ≤ 1, increment the removal counter and move the pointer forward by two positions to skip the resolved pair. Otherwise move forward by one. This ensures each character is processed at most once.
What is the best approach for Remove Adjacent Almost-Equal Characters?
The greedy approach is the most efficient solution. Scan the string from left to right and check adjacent characters. If their ASCII difference is ≤ 1, count one deletion and skip the next character to avoid overlapping conflicts. This produces the minimum removals in O(n) time and O(1) space.
Is Remove Adjacent Almost-Equal Characters asked at Google/Amazon/Meta?
Problems involving greedy string processing and adjacency constraints frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test the ability to detect local conflicts and resolve them using a greedy scan or dynamic programming reasoning.
What data structure is used in Remove Adjacent Almost-Equal Characters?
The solution mainly uses basic string traversal with index pointers. No advanced data structures are required for the optimal approach. The dynamic programming variant may use an array to store state values for each index.
What is the time complexity of Remove Adjacent Almost-Equal Characters?
The optimal greedy solution runs in O(n) time where n is the length of the string, because it scans the string once. Space complexity is O(1) since only a few counters and indices are used. A dynamic programming version also runs in O(n) time but requires O(n) extra memory.