String Processing
What is this?
Typing on a keyboard is like stacking letters in a pile: each key you press drops a letter on top, and hitting backspace removes the most recent one. A stack mirrors this perfectly — push a letter when you type it, pop the top off when you backspace. Whatever letters are left in the pile are the text you actually ended up with, which makes it easy to compare what two people really typed.
💡 Fun fact: The text box you are typing in right now keeps your input in a buffer and handles each backspace the same way — by removing the most recently entered character, just like popping the top off a stack.
🔓 The 1 problem in this chapter is free. Sign in with Google or Microsoft to start solving.
Core idea: When you "type" characters and some of them later get undone, a stack is the perfect editor: push each character, and let an undo signal (a backspace) pop the most recent one. The stack always holds exactly the text typed so far.
Why a stack models text editing
Editing is LIFO by nature: a backspace deletes the most recently typed character. That's a pop. So simulating a stream of keystrokes-with-backspaces is just: push real characters, pop on #. The stack, read bottom-to-top, is the final text.
The problem in this chapter
Backspace String Compare — do two keystroke logs type the same thing?
Given two strings where # means backspace, decide whether they produce identical final text. The natural solution builds each string with a stack and compares — but there's a slicker O(1)-space answer.
- Stack build (intuitive): fold each string into its final text, compare. O(n) time, O(n) space.
- Reverse two-pointer (optimal): a character's survival depends only on the backspaces that come after it — so scan each string from the right with a "skip debt" counter, comparing the surviving characters on the fly. O(n) time, O(1) space.
The stack is the intuition; the back-to-front two-pointer is the optimization. A
#you pass while scanning right adds one unit of deletion debt; the next real character pays it down instead of surviving.
The cross-cutting skill
| Approach | Mechanism | Space |
|---|---|---|
| Stack build | push chars, pop on #, compare results |
O(n) |
| Reverse scan | from the right, skip (debt) survivors as backspaces demand |
O(1) |
Many "process a stream with undo" problems have this shape: a stack gives the obvious answer, and a clever right-to-left or counter-based pass removes the extra buffer when the interviewer asks for O(1) space.
Where you'll meet it beyond the interview
- Text editors and terminals processing backspace/delete in an input buffer.
- Replaying an edit or keystroke log to reconstruct a final document state.
- Comparing two edit streams for equivalence (collaborative editing, diffing).
- Folding an event log where later events cancel earlier ones (idempotent compaction).
📓 Draw it yourself
- Type with a stack. Draw the stack as you process
"a#bc#d", pushing letters and popping on each#. The leftover stack is the final text. - Scan from the right. Draw two strings and walk a pointer right-to-left in each, keeping a small "skip" counter; mark each surviving character and compare them in lockstep.
Snap photos and embed them with the /host-diagrams skill.
Complexity at a glance
| Approach | Time | Space |
|---|---|---|
| Stack build | O(n) | O(n) |
| Reverse two-pointer | O(n) | O(1) |
Key takeaways
- Editing is LIFO: push a typed char, pop on backspace — the stack is the text-so-far.
- A backspace on empty does nothing — guard the pop.
- The O(1) follow-up scans from the right with a skip counter, because deletions only depend on what comes after a character.
- Equal final text ≠ equal inputs — different keystroke logs can land on the same string.
- Why this chapter matters: it mirrors real editor/terminal input handling and is a clean "intuitive stack → optimized two-pointer" progression interviewers love to walk through.
Problem: Backspace String Compare.