# 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

```java
// 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!