Recursively remove all adjacent duplicates

Medium

Problem

Remove every run of two or more equal adjacent characters. Repeat on the result until no adjacent duplicates remain, then return what is left.

Example 1

Input:  "azxxzy"
Output: "ay"

Removing "xx" gives "azzy". Removing "zz" gives "ay".

Also asked as: Recursively remove all adjacent duplicates

Test cases

Case 1

Input:    "azxxzy"
Expected: "ay"

Case 2

Input:    "geeksforgeeg"
Expected: "gksfor"

Case 3

Input:    "caaabbbaacdddd"
Expected: ""

Case 4

Input:    "aaa"
Expected: ""

Case 5

Input:    "abc"
Expected: "abc"

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Stack

Time O(n)Space O(n)

Push chars; if the incoming char equals the stack top, pop the whole run instead of pushing (and skip the rest of that run).

function removeAdjacentDuplicates(s) {
const st = [];
let i = 0;
while (i < s.length) {
if (st.length && st[st.length - 1] === s[i]) {
const dup = s[i];
while (i < s.length && s[i] === dup) i++;
st.pop();
} else {
st.push(s[i++]);
}
}
return st.join('');
}