What's the Problem Really Asking?
Imagine you're editing a text document and every time you type a number, it acts like a backspace key — it deletes itself AND the character just before it. That's exactly what this problem is!
Given a string like "cb34":
3deletesb→"c4"4deletesc→""
Simple idea, right? Let's look at all the ways to solve it.
Here is the problem link-: Leetcode 3174
Approach 1: Using a Stack (Classic & Intuitive)
The Idea
A stack is the most natural fit here. Think of it like a stack of plates:
- If the character is a letter → push it onto the stack (add a plate)
- If the character is a digit → pop from the stack (remove the top plate, the digit deletes itself too)
At the end, whatever's left on the stack is your answer.
Code
Real Life Analogy
Think of a Jenga tower. Every time a digit appears, it pulls out the topmost block (the closest left letter). At the end, whatever blocks remain standing — that's your result.
Complexity
- Time: O(n) — single pass through the string
- Space: O(n) — stack can hold up to n characters in worst case (no digits)
Approach 2: StringBuilder as a Stack (Optimal & Clean) ✅
The Idea
This is the smartest approach and the one you already have in your solution. A StringBuilder naturally behaves like a stack:
- Append letters to the end
- When a digit appears, delete the last character (
.deleteCharAt(sb.length() - 1))
No extra data structure needed!
Code
Walkthrough with Example
Let's trace "cb34" step by step:
| Step | Character | Action | StringBuilder |
| 1 | c | append | "c" |
| 2 | b | append | "cb" |
| 3 | 3 | delete last | "c" |
| 4 | 4 | delete last | "" |
Final answer: ""
Another example — "a1b2c3":
| Step | Character | Action | StringBuilder |
| 1 | a | append | "a" |
| 2 | 1 | delete last | "" |
| 3 | b | append | "b" |
| 4 | 2 | delete last | "" |
| 5 | c | append | "c" |
| 6 | 3 | delete last | "" |
Final answer: ""
Complexity
- Time: O(n) — one pass, each character processed once
- Space: O(n) — StringBuilder storage
Approach 3: Brute Force / Simulation (Beginner-Friendly)
The Idea
Just simulate exactly what the problem says — find the first digit, remove it and its closest left non-digit, repeat.
Complexity
- Time: O(n²) — for each digit found, we restart scanning from the beginning
- Space: O(n) — StringBuilder storage
This works fine for the given constraints (n ≤ 100), but it's not scalable for large inputs.
Approach Comparison
| Approach | Time | Space | Code Simplicity | Best For |
| Brute Force | O(n²) | O(n) | ⭐⭐⭐ | Understanding the problem |
| Stack | O(n) | O(n) | ⭐⭐⭐⭐ | Interviews (clear intent) |
| StringBuilder | O(n) | O(n) | ⭐⭐⭐⭐⭐ | Production / Best solution |
Key Takeaways
1. Recognize the Stack Pattern Anytime a problem says "delete the closest left element," your brain should immediately scream stack. This pattern appears in many problems like Valid Parentheses, Asteroid Collision, and Backspace String Compare.
2. StringBuilder is a hidden stack In Java, StringBuilder supports append() (push) and deleteCharAt(length-1) (pop). Using it directly instead of a Stack<Character> saves you the overhead of boxing/unboxing characters and the extra reverse step.
3. The problem guarantees all digits can be deleted This means you'll never call deleteCharAt on an empty StringBuilder. In a real interview, you'd still want to add a guard check (if (sb.length() > 0)) to be safe and show defensive coding habits.
Similar Problems to Practice
- 844. Backspace String Compare — almost identical concept
- 1047. Remove All Adjacent Duplicates In String — same stack pattern
- 2390. Removing Stars From a String — stars act as backspace, same idea
