Remove All Adjacent Duplicates in String II
Problem
Given a string s and an integer k, repeatedly remove any k adjacent identical characters until no more can be removed. Return the final string.
s = "deeedbbcccbdaa", k = 3"aa"def remove_duplicates(s, k):
stack = [] # list of [char, count]
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(ch * cnt for ch, cnt in stack)function removeDuplicates(s, k) {
const stack = []; // [char, count]
for (const c of s) {
if (stack.length && stack[stack.length - 1][0] === c) {
stack[stack.length - 1][1]++;
if (stack[stack.length - 1][1] === k) stack.pop();
} else {
stack.push([c, 1]);
}
}
return stack.map(([ch, cnt]) => ch.repeat(cnt)).join("");
}class Solution {
public String removeDuplicates(String s, int k) {
Deque<int[]> stack = new ArrayDeque<>(); // [char, count]
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek()[0] == c) {
stack.peek()[1]++;
if (stack.peek()[1] == k) stack.pop();
} else {
stack.push(new int[]{c, 1});
}
}
StringBuilder sb = new StringBuilder();
Iterator<int[]> it = stack.descendingIterator();
while (it.hasNext()) {
int[] e = it.next();
for (int i = 0; i < e[1]; i++) sb.append((char) e[0]);
}
return sb.toString();
}
}string removeDuplicates(string s, int k) {
vector<pair<char,int>> st;
for (char c : s) {
if (!st.empty() && st.back().first == c) {
st.back().second++;
if (st.back().second == k) st.pop_back();
} else {
st.push_back({c, 1});
}
}
string out;
for (auto& p : st) out.append(p.second, p.first);
return out;
}Explanation
Instead of repeatedly rescanning the string, we collapse runs in a single pass using a stack of [char, count] pairs. Each entry remembers a character and how many times it currently repeats in a row.
For each character c, if the top of the stack holds the same character, we just bump its count. The instant that count reaches k, the whole run is removed by popping that entry. If the top is a different character (or the stack is empty), we push a new pair [c, 1].
At the end, the stack holds the surviving runs in order, so we rebuild the answer by repeating each character its remaining count of times.
Example: s = "deeedbbcccbdaa", k = 3. The three es build up and pop, exposing the d before them; later ccc pops, then the freshly adjacent ds reach three and pop too, cascading down until only "aa" remains.
It works because storing counts lets a deletion instantly re-expose whatever was underneath, so newly adjacent equal characters merge correctly in the same pass — no repeated scanning needed.