Stack-Based String Problems – Intuition Cheat Sheet
When you're faced with tricky string problems that involve brackets, nested patterns, or context switching, there's a high chance a stack is your best friend. In this article, we break down the intuition behind stack-based string problems and give you a cheat sheet you can always come back to.
🧠 Why Stack?
Stacks are perfect when you need a Last-In-First-Out (LIFO) structure. That means when you go into a nested structure or a new "context," you can push it onto the stack, and when you're done, pop it back out in the correct order.
🔄 1. Decode String
Example: "3[a2[c]]" → "accaccacc"
🤔 Problem:
You're given a string with numbers and brackets. The goal is to decode it.
🕵️ Solution Intuition:
Use a count stack to store repeat numbers.
Use a string stack to store the previous string context.
When you hit ']', you pop the top count and string, repeat the current segment, and combine.
🔍 2. Valid Parentheses
Example: "({[]})" → Valid
📄 Problem:
Check if every opening bracket has a matching closing bracket.
🏛️ Solution Intuition:
Push opening brackets to the stack.
On closing bracket, check if it matches the top of the stack.
If mismatched or stack is not empty at end, it's invalid.
📊 3. Evaluate Reverse Polish Notation
Example: ["2", "1", "+", "3", "*"] → (2 + 1) * 3 = 9
🔎 Problem:
Evaluate a postfix expression.
⚖️ Solution Intuition:
Push numbers to the stack.
When an operator appears, pop the top two numbers, apply the operation, and push the result.
🔠 4. Simplify Unix-Style Path
Example: "/a/./b/../../c/" → "/c"
🤝 Problem:
Simplify a string representing a Unix-style path.
🔧 Solution Intuition:
Split the path by '/' and use a stack.
If you see "..", pop from the stack.
If you see a valid folder, push it.
Join the stack with '/' at the end.
🌟 5. Remove All Adjacent Duplicates
Example: "abbaca" → "ca"
❌ Problem:
Remove characters that appear consecutively.
🏠 Solution Intuition:
Use a stack.
If the current character matches the top, pop it.
Else, push it.
📌 Bonus: Quick Self-Checklist Before Choosing Stack
| Ask Yourself | If Yes, Use Stack? |
| Is there nesting or reversal involved? | ✅ Yes |
| Do I need to backtrack or undo something? | ✅ Yes |
| Are characters being grouped contextually? | ✅ Yes |
🔹 Common Patterns To Memorize
// Decode String
char = digit → store k
char = '[' → push k & current, reset current
char = letter → append to current
char = ']' → pop k & prev, repeat current and append
// Valid Parentheses
if opening bracket → push
if closing → match with top
// Postfix Eval
if number → push
if operator → pop 2, apply, push result
// Simplify Path
split by '/'
if ".." → pop
if valid folder → push
📚 Final Tip:
Practicing stack problems improves pattern recognition over time. Once you see brackets or nested structure, your brain will automatically say: "Stack time!"
Want to take it further? Try LeetCode problems like:
Decode String
Simplify Path
Valid Parentheses
Basic Calculator II
Remove All Adjacent Duplicates
Save this cheat sheet. It’s your Stack Survival Kit ⛏️ for string-based problems!
