Remove All Adjacent Duplicates in String II
Remove All Adjacent Duplicates in String II is a medium stack problem solved with the stack basics pattern.
The best approach, optimal (stack of character counts), runs in O(n) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (repeated scanning) up.
Problem
You are given a string s and an integer k. A removal deletes k neighbouring letters that are all the same; the parts on either side then join together, which may create a new run of equal letters.
Keep making removals until none is possible, and return the final string. The result does not depend on the order of the removals.
Examples
Example 1
- Input
s = "xyyyzzx", k = 3- Output
"xzzx"- Why
- Only yyy is a run of three equal letters. After it is removed, zz is still too short.
Example 2
- Input
s = "baaabbccc", k = 3- Output
""- Why
- Removing aaa joins b and bb into bbb. Removing bbb and ccc then leaves nothing.
Example 3
- Input
s = "pqqrrrqp", k = 3- Output
"pp"- Why
- Remove rrr to get pqqqp, then qqq to get pp, which is shorter than k.
Constraints
1 <= s.length <= 10^52 <= k <= 10^4scontains only lowercase English letters.
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 (3 examples, or your own). Submit also runs 12 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.
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 scanning) | O(n² / k) | O(n) |
| Optimal (stack of character counts) | O(n) | O(n) |
1Brute force (repeated scanning)
O(n² / k)Up to n / k removals, each followed by a scan and a rebuild of up to n characters.O(n)The rebuilt string.Scan the string counting the length of the current run of equal letters. As soon as a run reaches k, cut those k letters out and start scanning again from the beginning. Stop when a full scan finds no run of length k.
- run = 1; for i from 1: run = run + 1 if s[i] == s[i-1], else 1.
- If run == k: s = s[0 .. i-k] + s[i+1 ..]; restart the scan.
- If a scan finishes without removing anything, return s.
class Solution {
public String removeDuplicates(String s, int k) {
boolean changed = true;
while (changed) {
changed = false;
int run = 1;
for (int i = 1; i < s.length(); i++) {
run = s.charAt(i) == s.charAt(i - 1) ? run + 1 : 1;
if (run == k) {
s = s.substring(0, i - k + 1) + s.substring(i + 1);
changed = true;
break;
}
}
}
return s;
}
}class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
changed = True
while changed:
changed = False
run = 1
for i in range(1, len(s)):
run = run + 1 if s[i] == s[i - 1] else 1
if run == k:
s = s[:i - k + 1] + s[i + 1:]
changed = True
break
return sclass Solution {
public:
string removeDuplicates(string s, int k) {
bool changed = true;
while (changed) {
changed = false;
int run = 1;
for (int i = 1; i < (int)s.size(); i++) {
run = s[i] == s[i - 1] ? run + 1 : 1;
if (run == k) {
s.erase(i - k + 1, k);
changed = true;
break;
}
}
}
return s;
}
};function removeDuplicates(s, k) {
let changed = true;
while (changed) {
changed = false;
let run = 1;
for (let i = 1; i < s.length; i++) {
run = s[i] === s[i - 1] ? run + 1 : 1;
if (run === k) {
s = s.slice(0, i - k + 1) + s.slice(i + 1);
changed = true;
break;
}
}
}
return s;
}2Optimal (stack of character counts)
O(n)Each character is pushed or counted once, and the rebuild writes at most n characters.O(n)The stack and the output.Build the answer left to right in a stack where each entry is a character and the length of its current run. A new character either adds 1 to the top entry (same letter) or pushes a new entry with count 1. When the top count reaches k, pop it: the run disappears, and the entry below it is now on top, ready to continue a run if the next letter matches it.
- For each c in s: if the stack top has character c, increment its count; otherwise push (c, 1).
- If the top count equals k, pop it.
- Rebuild the string by writing each entry's character count times, from bottom to top.
class Solution {
public String removeDuplicates(String s, int k) {
int n = s.length(), top = 0;
char[] chars = new char[n];
int[] counts = new int[n];
for (int i = 0; i < n; i++) {
char c = s.charAt(i);
if (top > 0 && chars[top - 1] == c) {
if (++counts[top - 1] == k) top--;
} else {
chars[top] = c;
counts[top] = 1;
top++;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < top; i++)
for (int j = 0; j < counts[i]; j++) sb.append(chars[i]);
return sb.toString();
}
}class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = []
for c in s:
if stack and stack[-1][0] == c:
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
else:
stack.append([c, 1])
return ''.join(c * cnt for c, cnt in stack)class Solution {
public:
string removeDuplicates(string s, int k) {
vector<pair<char, int>> st;
for (char c : s) {
if (!st.empty() && st.back().first == c) {
if (++st.back().second == k) st.pop_back();
} else {
st.push_back({c, 1});
}
}
string out;
for (auto& [c, cnt] : st) out.append(cnt, c);
return out;
}
};function removeDuplicates(s, k) {
const chars = [], counts = [];
for (const c of s) {
const top = chars.length - 1;
if (top >= 0 && chars[top] === c) {
if (++counts[top] === k) {
chars.pop();
counts.pop();
}
} else {
chars.push(c);
counts.push(1);
}
}
let out = '';
for (let i = 0; i < chars.length; i++) out += chars[i].repeat(counts[i]);
return out;
}Edge cases to test
- Nothing to remove (the string is returned unchanged)
- Everything is removed (return the empty string)
- A run longer than k, like 5 equal letters with k = 3 (remove 3, keep 2)
- Chain reactions, where a removal makes two equal runs touch
Hints
Hint 1
The order in which you remove runs does not change the final string, so any repeated scan works, but it may rescan the string many times.
Hint 2
Process the string left to right with a stack. What should each stack entry remember besides the character?
Hint 3
Store (character, how many times in a row it appears). When a count reaches k, pop the entry; the characters before it are already in their final shape.
FAQ
What is the best time complexity for Remove All Adjacent Duplicates in String II?
Optimal (stack of character counts) runs in O(n) time and O(n) extra space. Each character is pushed or counted once, and the rebuild writes at most n characters.
Which pattern does Remove All Adjacent Duplicates in String II 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 II?
Yes. Brute force (repeated scanning) takes O(n² / k) time and O(n) space. Scan the string counting the length of the current run of equal letters.
Which edge cases should I test for Remove All Adjacent Duplicates in String II?
Nothing to remove (the string is returned unchanged); Everything is removed (return the empty string); A run longer than k, like 5 equal letters with k = 3 (remove 3, keep 2); Chain reactions, where a removal makes two equal runs touch.