LeetCode · #394
Decode String Solution
Given an encoded string like 3[a2[c]], return the decoded string "accaccacc".
01
Section One · Problem
Problem Statement
The encoding rule is k[encoded_string], where the encoded_string inside the brackets is repeated k times. Encoding can be nested. Decode the string and return it.
Example 1
Input: s = "3[a]2[bc]" Output: "aaabcbc"
Example 2
Input: s = "3[a2[c]]" Output: "accaccacc" // Inner: 2[c] → "cc". Then 3[acc] → "accaccacc"
Constraints
• 1 ≤ s.length ≤ 30 • s contains lowercase letters, digits, and brackets [ ] • 1 ≤ k ≤ 300 • Input is always valid — no extra/missing brackets
02
Section Two · Approach 1
Recursive Approach
Parse the string recursively. When you encounter a digit, read the full number, then recurse into the brackets to decode the inner string, and repeat it k times. This naturally handles nesting.
Both approaches are O(n):
- The recursive and stack-based solutions are equivalent — the call stack in recursion mirrors an explicit stack.
- The stack approach is often preferred for its clarity and avoidance of global index tracking.
03
Section Three · Approach 2
Stack — O(n)
Use two stacks (or a stack of pairs): one for the repeat count and one for the string built so far. When you hit [, save the current state and start fresh. When you hit ], pop the saved state and repeat the current string.
💡 Mental model: Imagine writing a letter with nested templates. When you encounter a number followed by '[', you put your current draft into a folder (stack) and start a new page. When you hit ']', you pull the folder out, copy the new page k times, and append it to the draft from the folder.
Algorithm
- Digit: Build the multi-digit number.
- '[': Push current string and current number onto stacks. Reset both.
- ']': Pop count and previous string. Append current string × count to previous string. Set current = result.
- Letter: Append to current string.
04
Section Four · Trace
Visual Walkthrough
Trace through "3[a2[c]]":
Stack — save context on '[', restore and repeat on ']'
05
Section Five · Implementation
Code — Java & Python
Java — Stack
import java.util.Stack;
class Solution {
public String decodeString(String s) {
Stack<String> strStack = new Stack<>();
Stack<Integer> countStack = new Stack<>();
StringBuilder cur = new StringBuilder();
int num = 0;
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0'); // multi-digit
} else if (c == '[') {
strStack.push(cur.toString());
countStack.push(num);
cur = new StringBuilder();
num = 0;
} else if (c == ']') {
String prev = strStack.pop();
int count = countStack.pop();
StringBuilder temp = new StringBuilder(prev);
for (int i = 0; i < count; i++) temp.append(cur);
cur = temp;
} else {
cur.append(c); // letter
}
}
return cur.toString();
}
}
Python — Stack
class Solution:
def decodeString(self, s: str) -> str:
str_stack = []
count_stack = []
cur = ""
num = 0 for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == '[':
str_stack.append(cur)
count_stack.append(num)
cur = ""
num = 0 elif c == ']':
prev = str_stack.pop()
count = count_stack.pop()
cur = prev + cur * count
else:
cur += c
return cur
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space | Trade-off |
|---|---|---|---|
| Stack ← optimal | O(n · maxK) | O(n) | n = output length. String repetition dominates. |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| No encoding | "abc" | No brackets or digits → return as-is. |
| Multi-digit k | "10[a]" | k=10, not 1 and 0 separately. Build num with num*10+digit. |
| Deep nesting | "2[a2[b2[c]]]" | Inner-first: c→cc, b+cc→bcc→bccbcc, etc. Stack depth = nesting level. |
| Adjacent groups | "2[a]3[b]" | "aabbb" — groups concatenate at the same level. |
| Letters between groups | "2[a]xy3[b]" | "aaxy bbb" — plain letters append directly to current string. |
⚠ Common Mistake: Assuming k is always a single digit. The constraint says k ≤ 300, so "100[ab]" is valid. Always accumulate digits:
num = num * 10 + digit until you hit '['.