Collapse Matching Neighbors
EasyStackFree
Problem
A string s of lowercase letters collapses like this: whenever two adjacent characters are equal, both disappear and the pieces on each side join up. This repeats until no two adjacent characters are equal.
Return the final string. The result does not depend on the order in which pairs are removed.
Example 1
- Input:
- s = "xyyxz"
- Output:
- "z"
Remove "yy" to get "xxz", then remove "xx" to get "z".
Example 2
- Input:
- s = "aaa"
- Output:
- "a"
One pair disappears, the third a has no partner left.
Example 3
- Input:
- s = "abc"
- Output:
- "abc"
Constraints
- 0 ≤ s.length ≤ 10^5
- s contains only lowercase English letters
Hint
Show the first hint
After a pair disappears, which two characters become new neighbours?
Walkthrough
How to approach it
01Clarify before coding
- Does a run of three equal letters vanish entirely? No: only pairs vanish, so "aaa" leaves "a".
- Is the answer unique regardless of removal order? Yes, so any correct strategy gives the same string.
02Brute force
Scan for any adjacent equal pair, delete it, and start the scan again until a full pass finds nothing.
Cost: Up to n/2 deletions, each with an O(n) scan and rebuild: O(n²) time.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.