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

---

🔹 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!