Remove All Adjacent Duplicates In String
Remove All Adjacent Duplicates In String is a easy stack problem solved with the stack basics pattern.
The best approach, optimal (stringbuilder as a stack), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeated scan) up.
Problem
Repeatedly remove two adjacent equal letters from the string until no such pair remains. Return the final string, which is always unique.
Examples
Example 1
- Input
s = "abbaca"- Output
"ca"- Why
- Remove bb → aaca, then aa → ca.
Example 2
- Input
s = "azxxzy"- Output
"ay"
Constraints
1 <= s.length <= 10^5- Lowercase letters only.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (repeated scan) | O(n²) | O(n) |
| Optimal (StringBuilder as a stack) | O(n) | O(n) |
1Brute force (repeated scan)
O(n²)O(n)Find the first adjacent equal pair, delete it, and rescan from the start until none is left.
- Scan for i with s[i] == s[i+1]; delete both; repeat.
class Solution {
public String removeDuplicates(String s) {
StringBuilder sb = new StringBuilder(s);
boolean changed = true;
while (changed) {
changed = false;
for (int i = 0; i + 1 < sb.length(); i++) {
if (sb.charAt(i) == sb.charAt(i + 1)) {
sb.delete(i, i + 2);
changed = true;
break;
}
}
}
return sb.toString();
}
}class Solution:
def removeDuplicates(self, s: str) -> str:
sb = list(s)
changed = True
while changed:
changed = False
for i in range(len(sb) - 1):
if sb[i] == sb[i + 1]:
del sb[i:i + 2]
changed = True
break
return "".join(sb)class Solution {
public:
string removeDuplicates(string s) {
string sb = s;
bool changed = true;
while (changed) {
changed = false;
for (int i = 0; i + 1 < (int)sb.size(); i++) {
if (sb[i] == sb[i + 1]) {
sb.erase(i, 2);
changed = true;
break;
}
}
}
return sb;
}
};function removeDuplicates(s) {
const sb = s.split("");
let changed = true;
while (changed) {
changed = false;
for (let i = 0; i + 1 < sb.length; i++) {
if (sb[i] === sb[i + 1]) {
sb.splice(i, 2);
changed = true;
break;
}
}
}
return sb.join("");
}2Optimal (StringBuilder as a stack)
O(n)O(n)Build the result as a stack of kept characters. If the next character equals the top, pop it (the pair cancels); otherwise push it.
- For each c: if the last kept char == c, delete it; else append c.
class Solution {
public String removeDuplicates(String s) {
StringBuilder sb = new StringBuilder();
for (char c : s.toCharArray()) {
int n = sb.length();
if (n > 0 && sb.charAt(n - 1) == c) sb.deleteCharAt(n - 1);
else sb.append(c);
}
return sb.toString();
}
}class Solution:
def removeDuplicates(self, s: str) -> str:
sb = []
for c in s:
n = len(sb)
if n > 0 and sb[n - 1] == c:
sb.pop()
else:
sb.append(c)
return "".join(sb)class Solution {
public:
string removeDuplicates(string s) {
string sb;
for (char c : s) {
int n = sb.size();
if (n > 0 && sb[n - 1] == c) sb.pop_back();
else sb.push_back(c);
}
return sb;
}
};function removeDuplicates(s) {
const sb = [];
for (const c of s) {
const n = sb.length;
if (n > 0 && sb[n - 1] === c) sb.pop();
else sb.push(c);
}
return sb.join("");
}Edge cases to test
- Everything cancels (empty result)
- Removals that create new adjacent pairs
Hints
Hint 1
When you read a character, the only thing that matters is the last character still kept.
FAQ
What is the best time complexity for Remove All Adjacent Duplicates In String?
Optimal (StringBuilder as a stack) runs in O(n) time and O(n) extra space.
Which pattern does Remove All Adjacent Duplicates In String use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Remove All Adjacent Duplicates In String?
Yes. Brute force (repeated scan) takes O(n²) time and O(n) space. Find the first adjacent equal pair, delete it, and rescan from the start until none is left.
Which edge cases should I test for Remove All Adjacent Duplicates In String?
Everything cancels (empty result); Removals that create new adjacent pairs.