Resulting String After Adjacent Removals - Solution & Explanation

Problem Overview: You are given a string and repeatedly remove adjacent character pairs that satisfy the removal rule defined in the problem. After no more valid adjacent pairs exist, return the final resulting string.

Approach 1: Repeated String Simulation (Brute Force) (Time: O(n^2), Space: O(n))

The most direct method repeatedly scans the string and removes adjacent pairs whenever they satisfy the removal condition. After each removal, the string shrinks and the scan restarts because new removable pairs may appear. This simulates the process exactly as described. The downside is efficiency: each removal can trigger another full pass over the string, leading to quadratic time in the worst case. This approach is useful for understanding the mechanics of the problem but is rarely acceptable for large inputs.

Approach 2: Stack-Based Simulation (Time: O(n), Space: O(n))

A stack models the removal process efficiently. Iterate through the string once. For each character, compare it with the character at the top of the stack. If the two characters form a removable adjacent pair according to the rule, pop the stack (which simulates removing the pair). Otherwise, push the current character onto the stack. This works because any newly formed adjacency after a removal will automatically be checked with the next incoming character.

The key insight: removals only depend on the most recent unresolved character. A stack preserves exactly that state. Each character is pushed once and popped at most once, giving linear time complexity. This turns what looks like repeated rescanning into a single pass simulation.

After processing the entire string, the stack contains the remaining characters in order. Join them to produce the resulting string. The algorithm processes each character once, making it optimal for large inputs.

This problem is a classic pattern combining string processing with a stack to handle pair cancellations. The same technique appears in problems involving bracket validation, adjacent duplicate removal, and collision simulations.

Recommended for interviews: The stack-based solution is what interviewers expect. The brute force simulation demonstrates that you understand the removal process, but the stack approach shows algorithmic maturity by converting repeated rescans into a single linear pass.