Stacks and Monotonic Structures
Most recent first
The stack is the answer whenever the thing you opened last is the thing that must close first.
Key idea
The signal to look for
A stack is a list you only touch at one end. append puts something on top, pop takes the top off, and stack[-1] looks at the top without removing it. In Python a plain list is a stack; there is no separate type to import.
The signal that a problem wants one is nesting. Whenever the most recently opened thing has to be resolved before anything older, the structure you need is a stack, because that is precisely the order a stack gives you.
Gotcha
Popping an empty stack raises
[].pop() raises IndexError, and so does [][-1]. Every place you inspect or remove the top needs to have established that something is there.
The usual shape is if stack and stack[-1] == something. Python's and stops at the first false part, so the emptiness check protects the index that follows it. Writing those two tests in the other order raises on empty input.
Collapsing adjacent pairs
Here is the pattern on a problem with no brackets in it. Repeatedly remove adjacent identical characters until none remain, so abbaca collapses to ca.
A stack does this in one pass. Each incoming character either cancels the top or joins it.
Why it works
Why one pass is enough
The second example is the interesting one. Removing xx puts two zs next to each other, which then cancel, which puts a and y together. Repeatedly scanning the string would take several passes.
The stack gets it in one because after a pop, the new top is exactly the character that is now adjacent to the incoming one. The structure keeps the neighbor relationship correct for free, which is the recurring reason stacks turn multi-pass problems into single-pass ones.
A second example with no symmetry
Stacks are not only for matching pairs. Resolving a path with .. segments is the same shape: .. undoes the most recent directory, which is exactly a pop.
Edge cases
Guard the pop, do not assume balance
/../.. tries to step above the root. The if stack guard makes that a no-op rather than a crash. Real inputs are frequently unbalanced, and deciding what unbalanced means before you write the loop is most of the work in this family.
For the problem below, that decision is the whole problem: what should happen when a closer arrives with nothing to match, and what should happen when the input ends with things still open? Those are two different failures and both must be handled.
Predict the output: guard order
This checks the top before checking emptiness. Type what it prints, including the exception name if it raises one.
Stack drills
Three one-pass stack problems. collapse_k removes runs of exactly k identical adjacent characters, repeatedly. undo_history applies a list of actions where undo cancels the most recent surviving action. is_balanced_single checks a string containing only ( and ).
Tests
print(collapse_k("deeedbbcccbdaa", 3))
print(undo_history(["open", "type", "undo", "save", "undo", "undo", "undo"]))
print(is_balanced_single("(())"), is_balanced_single("())("), is_balanced_single("(("))Output
Run the tests when you are ready.
Valid Parentheses
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.