Remove All Adjacent Duplicates in String II — Solution
Remove All Adjacent Duplicates in String II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Remove All Adjacent Duplicates in String II is a medium coding problem on strings and stack, asked in Amazon, Google and Bloomberg interviews.
- Difficulty: Medium
- Topics: Strings, Stack
- Asked at: Amazon, Google, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a string s and an integer k. A k-duplicate removal deletes k adjacent and equal characters from s, joining what is left.
Repeat the removal until it is no longer possible and return the final string. The answer is unique.
Example 1
Input: s = "abcd", k = 2
Output: abcd
Explanation: Nothing to remove.
Example 2
Input: s = "deeedbbcccbdaa", k = 3
Output: aa
Example 3
Input: s = "pbbcggttciiippooaais", k = 2
Output: ps
Constraints
1 <= s.length <= 402 <= k <= 6s consists of lowercase English letters.
Hints for Remove All Adjacent Duplicates in String II
Hint 1
Deleting characters can make new runs adjacent, so a single scan with a stack is the clean approach.
Hint 2
Store pairs of (character, run length) on the stack instead of individual characters.
Hint 3
When a run length hits
k, pop the whole frame — the frames below then become adjacent automatically.
How to solve Remove All Adjacent Duplicates in String II
Stack of (character, run length) frames; extend the top when the character matches, pop the frame when its length reaches k.
Approach
- For each
ch: increment the top's count if it matches, else push[ch, 1]. - If the top's count equals
k, pop it. - Expand the frames into the answer.
Why it works
Removing a run can join the runs on either side, and the frame stack keeps the left neighbour on top so the join is detected on the next character.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Storing individual characters instead of counts makes the
k-checkO(k)each time.
Reference solution
Python
def removeDuplicates(s: str, k: int) -> str:
stack = []
for ch in s:
if stack and stack[-1][0] == ch:
stack[-1][1] += 1
else:
stack.append([ch, 1])
if stack[-1][1] == k:
stack.pop()
return "".join(ch * count for ch, count in stack)Java
public static String removeDuplicates(String s, int k) {
List<Character> chars = new ArrayList<>();
List<Integer> counts = new ArrayList<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (!chars.isEmpty() && chars.get(chars.size() - 1) == c) {
counts.set(counts.size() - 1, counts.get(counts.size() - 1) + 1);
} else {
chars.add(c);
counts.add(1);
}
if (counts.get(counts.size() - 1) == k) {
chars.remove(chars.size() - 1);
counts.remove(counts.size() - 1);
}
}
StringBuilder out = new StringBuilder();
for (int i = 0; i < chars.size(); i++) {
for (int j = 0; j < counts.get(i); j++) out.append(chars.get(i));
}
return out.toString();
}C++
string removeDuplicates(string s, int k) {
vector<char> chars;
vector<int> counts;
for (char c : s) {
if (!chars.empty() && chars.back() == c) {
counts.back()++;
} else {
chars.push_back(c);
counts.push_back(1);
}
if (counts.back() == k) {
chars.pop_back();
counts.pop_back();
}
}
string out;
for (size_t i = 0; i < chars.size(); i++) {
out.append((size_t) counts[i], chars[i]);
}
return out;
}JavaScript
var removeDuplicates = function(s, k) {
const chars = [], counts = [];
for (let i = 0; i < s.length; i++) {
const c = s.charAt(i);
if (chars.length > 0 && chars[chars.length - 1] === c) {
counts[counts.length - 1]++;
} else {
chars.push(c);
counts.push(1);
}
if (counts[counts.length - 1] === k) {
chars.pop();
counts.pop();
}
}
let out = "";
for (let i = 0; i < chars.length; i++) {
for (let j = 0; j < counts[i]; j++) out += chars[i];
}
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Stack Data Structure