Resulting String After Adjacent Removals

Resulting String After Adjacent Removals

What is this problem about?

The Resulting String After Adjacent Removals interview question gives you a string and asks you to repeatedly remove any pair of adjacent characters that are consecutive in the alphabet (e.g., 'a' and 'b', or 'y' and 'z'). You must keep removing such pairs until no more adjacent consecutive-alphabet pairs exist, then return the resulting string.

Why is this asked in interviews?

Meta asks this stack-based simulation problem because it is a natural extension of the classic "remove adjacent duplicates" problem, but with a more nuanced condition. It tests the candidate's ability to apply a stack for real-time character processing with a custom removal condition. This pattern appears in text normalization, expression simplification, and bracket matching systems.

Algorithmic pattern used

The pattern is stack simulation with a custom adjacency condition. Process the string character by character. For each character: check if the stack is non-empty and the top of the stack and the current character are alphabetically consecutive (i.e., abs(ord(current) - ord(stack_top)) == 1). If yes, pop the stack (removing the adjacent pair). If no, push the current character. After processing all characters, join the stack to form the result.

Example explanation

Input: "abcba"

• 'a': stack empty → push. Stack: [a]
• 'b': |ord('b') - ord('a')| = 1 → consecutive → pop 'a'. Stack: []
• 'c': stack empty → push. Stack: [c]
• 'b': |ord('b') - ord('c')| = 1 → consecutive → pop 'c'. Stack: []
• 'a': stack empty → push. Stack: [a]

Result: "a".

Input: "cd":

• 'c': push. Stack: [c]
• 'd': |ord('d') - ord('c')| = 1 → pop. Stack: []

Result: "".

Common mistakes candidates make

• Processing pairs sequentially without using a stack, missing cascading removals (where a removal creates a new adjacent pair).
• Using ord(a) - ord(b) == 1 (only one direction) instead of abs(ord(a) - ord(b)) == 1 (both 'a','b' and 'b','a' should match).
• Joining the stack in the wrong order — Python's list stack should be joined directly since elements are appended left-to-right.
• Forgetting that 'a' and 'z' are NOT consecutive alphabetically (they don't wrap around).

Interview preparation tip

For the Resulting String After Adjacent Removals coding problem, the string and stack simulation interview pattern is optimal. The stack handles cascading removals naturally — each push/pop decision is O(1) and the total time is O(n). Meta interviewers may ask: "Why doesn't a simple scan-and-remove loop work?" — the answer is that a single scan misses newly created pairs after removals. The stack processes everything in one O(n) pass.