70. Recursively Remove Adjacent Duplicate Characters

Given a string s, repeatedly remove any pair of adjacent identical characters (removing a pair can create a new adjacent pair, which should also be removed) until no two adjacent characters are equal. Print the final string, or print 'EMPTY' if everything gets removed.

Input: The input is a single line containing the string s. Output: Print the final string after all adjacent-duplicate removals, or print 'EMPTY' if the whole string cancels out.

1 <= |s| <= 10^5

If the ENTIRE string collapses away through this process, the problem explicitly requires printing 'EMPTY' rather than an actual empty string - an easy edge case to overlook.

Repeatedly delete any pair of matching neighboring letters, and keep doing so - since removing one pair can create a NEW neighboring pair - until nothing more can be removed. Brute force: Repeatedly scan the whole string for any adjacent matching pair, remove it, and start scanning again from the beginning - this correctly handles the 'removal creates a new pair' chain reaction, but can cost O(n²) since each removal potentially re-scans the whole string. Optimised: A stack handles the chain-reaction automatically and in a SINGLE pass: whenever a new character matches the stack's current top, popping immediately and correctly exposes whatever was BELOW that top as the new 'neighbor' for the next character - exactly capturing the cascading removal effect without ever re-scanning from the start.

Write a recursive function that scans the string once to find the first adjacent duplicate pair, constructs a new (shorter) string with that pair removed, and calls itself again on this new string, with the base case being 'no adjacent duplicate pair found'. This is a genuinely recursive formulation (matching the problem's 'recursively' framing) rather than an explicit manual loop, but each recursive call still rebuilds a new string of roughly the same length, so the asymptotic cost doesn't improve over the repeated-scan approach - it mainly trades an explicit restart loop for call-stack-driven repetition. Time: O(n^2) Space: O(n) recursion depth plus O(n) per rebuilt string

Scan the string exactly once from left to right, maintaining a stack of characters processed so far. For each new character, if it equals the character on top of the stack, pop the stack (cancelling that adjacent pair); otherwise push the new character. Because popping a match immediately exposes whatever character was underneath, this automatically and correctly cascades removals (e.g. 'aabccba' collapses fully) without ever needing to rescan or recurse - the stack's current contents at any moment are exactly the fully-reduced string built so far. The final stack (bottom to top) is the answer, or 'EMPTY' if it ends up empty. Time: O(n) Space: O(n)

Repeatedly scan the string from the beginning looking for the first pair of adjacent identical characters; when found, remove that pair (producing a shorter string, which may create a brand-new adjacent pair at the join point) and restart the scan from the beginning again. Keep repeating until a full scan finds no adjacent duplicates. This directly matches the problem's description ('repeatedly remove... until no two adjacent characters are equal') but restarting the scan from the start every single time is wasteful, especially for inputs that cascade (e.g. long runs of the same character). Time: O(n^2) or worse in cascading cases Space: O(n)

1. Use a stack: for each character, if it matches the character currently on top of the stack, POP the stack instead of pushing (this represents removing the matching pair). 2. If it doesn't match (or the stack is empty), push the character normally. 3. After processing the whole string, whatever remains in the stack (bottom to top) is the final answer.

Time: O(n) - a single linear pass through the string, with O(1) push/pop at each character. Space: O(n) in the worst case, for the stack.

A string that fully cancels down to nothing ('EMPTY'); a removal that exposes a new adjacent pair which must also be removed (cascading); s up to 10^5 characters for performance.

Be ready to explain explicitly WHY a stack naturally handles the 'removal creates a new adjacent pair' cascading behavior - this is the single key insight that makes an O(n) solution possible instead of a slower repeated-rescanning approach.