Recursively remove all adjacent duplicates
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"
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('');}