String Processing

What is this?

Every problem here is a single left-to-right pass where the stack holds what is still open, or still liable to be cancelled. Adjacent duplicates cancel; unmatched brackets are removed; nested groups score; a Lisp expression's scopes stack up and unwind. In each case you never look backwards through the string — whatever needs revisiting is already sitting on the stack, in the right order.

💡 Fun fact: Score of Parentheses has a solution so short it looks wrong: track the current depth, and every time you see () add 2^depth to the answer. No stack at all. It works because scoring is distributive — the nesting multiplies each innermost pair by a power of two, and summing those contributions independently gives the same total. That is the same "count each atom's contribution" move as the monotonic-stack chapter, and it is worth recognising the family resemblance.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

---

The one-line idea: push what is unresolved, pop when it resolves, and the stack's contents at the end are the answer — the survivors, the unmatched positions, or the accumulated score.

---

1. Push the pair, not the character

Removing k adjacent duplicates naively means re-scanning after each removal, which is quadratic. Push (character, run length) instead:

The cascade is the point. Removing ccc brings a b next to bb, which removes and brings a d next to dd. Counting on the stack makes each cascade automatic rather than requiring another pass.

2. The stack as a record of what to delete

Minimum Remove to Make Valid Parentheses does not build the answer on the stack — it collects indices to remove. Push the index of every (; on a ), pop if the stack is non-empty, otherwise mark this ) as unmatched. Whatever indices remain on the stack at the end are unmatched (. Delete both sets in one final pass.

This inversion — using the stack to record failures rather than successes — is worth having in your repertoire.

3. Scopes and bindings

Parse Lisp Expression is the hardest problem in the chapter, and the stack holds scopes. A let introduces bindings that shadow outer ones and must disappear when its expression closes. The clean structure is a stack of dictionaries: look up a variable by scanning from the innermost scope outward, and pop the whole frame when the expression ends. That is exactly how a real interpreter handles lexical scope.

---

4. Where you'll actually meet this

• Editors and IDEs. Bracket matching, auto-close, and "highlight the unmatched paren" are this exact scan.
• Linters and formatters. Detecting and repairing unbalanced delimiters, and computing nesting depth for indentation.
• Interpreters. Scope chains for variable lookup are a stack of dictionaries, precisely as above.
• Text sanitisation. Collapsing repeated characters and stripping malformed markup before rendering user content.
• Protocol and log parsing. Nested framing formats unwind with the same push/pop discipline.

---

5. Problems in this chapter

▶ Score of Parentheses

Score a balanced string where () is 1, AB is A+B, and (A) is 2*A. Either stack the enclosing frame's score, or use the depth trick and sum 2^depth per innermost pair.
Pattern: stack of frame scores (or depth contribution). Target: O(n) time, O(n) or O(1) space.

▶ Minimum Remove to Make Valid Parentheses

Remove the fewest characters to balance the string. Stack the indices of unmatched (, mark unmatched ) as you go, delete both sets at the end.
Pattern: stack of failure positions. Target: O(n) time, O(n) space.

▶ Remove All Adjacent Duplicates in String II

Delete every run of exactly k equal adjacent characters, repeatedly. Push (char, count) so cascades resolve in one pass.
Pattern: stack of (value, run length). Target: O(n) time, O(n) space.

▶ Check If Word Is Valid After Substitutions

Decide whether a string can be built by repeatedly inserting "abc". Push characters and pop a completed abc whenever a c closes one.
Pattern: stack as a partial-match buffer. Target: O(n) time, O(n) space.

▶ Parse Lisp Expression

Evaluate a small Lisp with let, add and mult. A stack of scopes handles shadowing and cleanup.
Pattern: scope stack + recursive evaluation. Target: O(n) time, O(depth) space.

---

6. Common pitfalls 🚫

• Rescanning after each removal. Cascades must be handled by the stack, not by looping until the string stops changing — that is O(n²) at best.
• Storing characters without counts. Runs need lengths; a character-only stack forces re-counting.
• Building the result string inside the loop. Collect on the stack and join once at the end.
• Deleting by index while iterating. Collect the indices, then build the survivors in a single pass — mutating the string as you go invalidates every later index.
• Forgetting leftover unmatched (. They are still on the stack when the scan ends and must be removed too.
• Assuming 2^depth is safe for arbitrary input. For Score of Parentheses the depth is bounded by the problem, but say so rather than leaving it implicit.
• Letting let bindings leak. In the Lisp evaluator, a scope must be popped when its expression ends, or an inner binding silently shadows outward.

---

7. Key takeaways

1. One pass, and the stack holds the unresolved. Everything you might have to revisit is already at hand, in order.
2. Push pairs when runs matter. (char, count) makes cascading deletions automatic.
3. A stack can record what to remove, not only what to keep.
4. Scopes are a stack of dictionaries — the standard way real interpreters implement lexical scope.
5. Look for a distributive shortcut. When a score decomposes per atom, depth arithmetic can replace the stack entirely.
6. Collect, then build. Never mutate the string mid-scan.
7. Why interviewers like it: these look like string puzzles and are really tests of whether you can spot the "open until resolved" structure and handle every cascade correctly in one pass.

Order: Score of Parentheses → Minimum Remove to Make Valid Parentheses → Remove All Adjacent Duplicates in String II → Check If Word Is Valid After Substitutions → Parse Lisp Expression.