109. Decode String
🔗 LeetCode Problem: 394. Decode String
📊 Difficulty: Medium
🏷️ Topics: Stack, String, Recursion
Problem Statement
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
The test cases are generated so that the length of the output will never exceed 10^5.
Example 1:
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Example 2:
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Example 4:
Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"
Constraints:
- 1 <= s.length <= 30
- s consists of lowercase English letters, digits, and square brackets '[]'.
- s is guaranteed to be a valid input.
- All the integers in s are in the range [1, 300].
🌟 ELI5: The Simple Idea!
Think of unpacking nested instructions:
"3[a]" means:
Repeat 'a' three times
Result: "aaa"
"2[abc]" means:
Repeat 'abc' two times
Result: "abcabc"
"3[a2[c]]" means:
Inner first: 2[c] = "cc"
Then: 3[acc] = "accaccacc"
The Stack Analogy:
Like reading parentheses - work inside out!
"3[a2[c]]"
↑
Start with innermost: 2[c] = "cc"
"3[acc]"
↑
Then outer: 3[acc] = "accaccacc"
Stack helps track nesting levels!
🎨 Visual Understanding
Example 1: Simple Pattern
Input: s = "3[a]2[bc]"
Character by character:
'3' → Number, store it
'[' → Start encoding block
'a' → Letter to repeat
']' → End block, repeat 'a' 3 times = "aaa"
'2' → Number, store it
'[' → Start encoding block
'bc' → Letters to repeat
']' → End block, repeat 'bc' 2 times = "bcbc"
Concatenate: "aaa" + "bcbc" = "aaabcbc" ✓
Example 2: Nested Pattern
Input: s = "3[a2[c]]"
Layer by layer:
Outer layer: 3[...]
Must decode inside first!
Inner layer: 2[c]
Decode: "cc"
Replace inner in outer: 3[acc]
Decode: "accaccacc" ✓
Stack visualization:
Read: 3 [ a 2 [ c ] ]
↓ ↓ ↓
Step 1: See '3', store number
Step 2: See '[', start new context
Step 3: See 'a', building string
Step 4: See '2', store number (nested)
Step 5: See '[', start nested context
Step 6: See 'c', building nested string
Step 7: See ']', close nested: 2×"c"="cc"
Step 8: Merge: "a"+"cc"="acc"
Step 9: See ']', close outer: 3×"acc"="accaccacc"
🎯 Approach 1: Two Stacks ⭐⭐⭐
The Standard Solution
Algorithm:
Use two stacks:
1. countStack: stores repeat counts
2. stringStack: stores previous strings
Process each character:
- Digit: build number (handle multi-digit)
- '[': push count and current string to stacks
- ']': pop count and string, repeat, merge
- Letter: append to current string
Implementation
/**
* Two-stack approach
* Time: O(maxK × n) where maxK is max repeat count
* Space: O(n)
*/
public String decodeString(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<String> stringStack = new Stack<>();
String currentString = "";
int k = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
// Build multi-digit number
k = k * 10 + (ch - '0');
} else if (ch == '[') {
// Push current state and start new level
countStack.push(k);
stringStack.push(currentString);
// Reset for new encoding block
currentString = "";
k = 0;
} else if (ch == ']') {
// Pop and decode
int repeatCount = countStack.pop();
StringBuilder decodedString = new StringBuilder(stringStack.pop());
// Repeat current string
for (int i = 0; i < repeatCount; i++) {
decodedString.append(currentString);
}
currentString = decodedString.toString();
} else {
// Regular letter
currentString += ch;
}
}
return currentString;
}
⏰ Time: O(maxK × n) where maxK is max repeat count
💾 Space: O(n) - Stack storage
Using StringBuilder (More Efficient)
public String decodeString(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<StringBuilder> stringStack = new Stack<>();
StringBuilder current = new StringBuilder();
int k = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
k = k * 10 + (ch - '0');
} else if (ch == '[') {
countStack.push(k);
stringStack.push(current);
current = new StringBuilder();
k = 0;
} else if (ch == ']') {
StringBuilder temp = current;
current = stringStack.pop();
int repeatCount = countStack.pop();
for (int i = 0; i < repeatCount; i++) {
current.append(temp);
}
} else {
current.append(ch);
}
}
return current.toString();
}
🔍 Super Detailed Dry Run
Example: s = "3[a2[c]]"
Goal: Decode nested pattern
═══════════════════════════════════════════════════════════════
Initialization
═══════════════════════════════════════════════════════════════
countStack = []
stringStack = []
currentString = ""
k = 0
═══════════════════════════════════════════════════════════════
Iteration 1: ch = '3'
═══════════════════════════════════════════════════════════════
Check: isDigit('3')? Yes
Action: Build number
k = k * 10 + ('3' - '0')
k = 0 * 10 + 3
k = 3
State:
countStack: []
stringStack: []
currentString: ""
k: 3
═══════════════════════════════════════════════════════════════
Iteration 2: ch = '['
═══════════════════════════════════════════════════════════════
Check: ch == '['? Yes
Action: Start new encoding level
countStack.push(k) → countStack.push(3)
stringStack.push(currentString) → stringStack.push("")
currentString = ""
k = 0
State:
countStack: [3]
stringStack: [""]
currentString: ""
k: 0
Explanation:
We're entering a new level of nesting
Save the repeat count (3)
Save any prefix string ("")
Reset for new context
═══════════════════════════════════════════════════════════════
Iteration 3: ch = 'a'
═══════════════════════════════════════════════════════════════
Check: isDigit? No, '['? No, ']'? No
Action: Regular letter
currentString += 'a'
currentString = "a"
State:
countStack: [3]
stringStack: [""]
currentString: "a"
k: 0
═══════════════════════════════════════════════════════════════
Iteration 4: ch = '2'
═══════════════════════════════════════════════════════════════
Check: isDigit('2')? Yes
Action: Build number
k = k * 10 + ('2' - '0')
k = 0 * 10 + 2
k = 2
State:
countStack: [3]
stringStack: [""]
currentString: "a"
k: 2
═══════════════════════════════════════════════════════════════
Iteration 5: ch = '['
═══════════════════════════════════════════════════════════════
Check: ch == '['? Yes
Action: Start nested level
countStack.push(k) → countStack.push(2)
stringStack.push(currentString) → stringStack.push("a")
currentString = ""
k = 0
State:
countStack: [3, 2]
stringStack: ["", "a"]
currentString: ""
k: 0
Explanation:
Entering NESTED encoding
Save repeat count (2)
Save prefix "a"
Reset for innermost context
═══════════════════════════════════════════════════════════════
Iteration 6: ch = 'c'
═══════════════════════════════════════════════════════════════
Check: Regular letter
Action: Append
currentString += 'c'
currentString = "c"
State:
countStack: [3, 2]
stringStack: ["", "a"]
currentString: "c"
k: 0
═══════════════════════════════════════════════════════════════
Iteration 7: ch = ']' (First closing bracket)
═══════════════════════════════════════════════════════════════
Check: ch == ']'? Yes
Action: Close innermost level
repeatCount = countStack.pop() = 2
prevString = stringStack.pop() = "a"
decodedString = prevString = "a"
for (i = 0; i < 2; i++) {
decodedString += currentString
}
Iteration 1: decodedString = "a" + "c" = "ac"
Iteration 2: decodedString = "ac" + "c" = "acc"
currentString = "acc"
State:
countStack: [3]
stringStack: [""]
currentString: "acc"
k: 0
Explanation:
We decoded "2[c]" = "cc"
Merged with previous "a" = "acc"
Back to outer level
═══════════════════════════════════════════════════════════════
Iteration 8: ch = ']' (Second closing bracket)
═══════════════════════════════════════════════════════════════
Check: ch == ']'? Yes
Action: Close outer level
repeatCount = countStack.pop() = 3
prevString = stringStack.pop() = ""
decodedString = prevString = ""
for (i = 0; i < 3; i++) {
decodedString += currentString
}
Iteration 1: decodedString = "" + "acc" = "acc"
Iteration 2: decodedString = "acc" + "acc" = "accacc"
Iteration 3: decodedString = "accacc" + "acc" = "accaccacc"
currentString = "accaccacc"
State:
countStack: []
stringStack: []
currentString: "accaccacc"
k: 0
Explanation:
We decoded "3[acc]" = "accaccacc"
No more nesting
Result complete!
═══════════════════════════════════════════════════════════════
Final Result
═══════════════════════════════════════════════════════════════
Return: currentString = "accaccacc" ✓
Example 2: s = "3[a]2[bc]"
'3' → k=3
'[' → Push count=3, string="", reset
'a' → current="a"
']' → Decode: ""+"a"×3="aaa", current="aaa"
'2' → k=2
'[' → Push count=2, string="aaa", reset
'b' → current="b"
'c' → current="bc"
']' → Decode: "aaa"+"bc"×2="aaabcbc"
Result: "aaabcbc" ✓
🎯 Approach 2: Recursion
Alternative Solution
/**
* Recursive approach
* Time: O(maxK × n), Space: O(n)
*/
private int index = 0;
public String decodeString(String s) {
StringBuilder result = new StringBuilder();
while (index < s.length() && s.charAt(index) != ']') {
if (!Character.isDigit(s.charAt(index))) {
// Regular letter
result.append(s.charAt(index++));
} else {
// Number found, build it
int k = 0;
while (index < s.length() && Character.isDigit(s.charAt(index))) {
k = k * 10 + (s.charAt(index++) - '0');
}
// Skip '['
index++;
// Recursively decode the substring
String decodedString = decodeString(s);
// Skip ']'
index++;
// Repeat the decoded string k times
for (int i = 0; i < k; i++) {
result.append(decodedString);
}
}
}
return result.toString();
}
🎯 Why This Solution Works
The Key Insight
Why stack for nested patterns?
Brackets create nesting levels:
3[a2[c]]
└──┴─ Inner level (must decode first)
└────── Outer level (uses inner result)
Stack naturally handles LIFO:
- Push state when entering [
- Pop state when exiting ]
- Innermost ] pops most recent [
This matches the nesting structure!
Understanding the State
What we track at each level:
1. Count: How many times to repeat
2. Previous string: What came before this block
Example: "abc3[x2[y]]def"
Level 0: prefix="abc", count=N/A
Enter: 3[...]
Level 1: prefix="", count=3
Add 'x' → prefix="x"
Enter: 2[...]
Level 2: prefix="", count=2
Add 'y' → prefix="y"
Exit: repeat "y" 2 times = "yy"
Back to Level 1:
Merge: prefix="x" + "yy" = "xyy"
Exit: repeat "xyy" 3 times = "xyyxyyxyy"
Back to Level 0:
Merge: "abc" + "xyyxyyxyy" + "def"
Result: "abcxyyxyyxyydef"
Multi-Digit Numbers
CRITICAL: Handle numbers like "12" or "100"
Wrong:
k = ch - '0' // Only handles single digit!
Correct:
if (isDigit(ch)) {
k = k * 10 + (ch - '0');
}
Example: "12[a]"
'1': k = 0*10 + 1 = 1
'2': k = 1*10 + 2 = 12 ✓
⚠️ Common Mistakes
Mistake 1: Not handling multi-digit numbers
// ❌ WRONG - Only handles single digit!
if (Character.isDigit(ch)) {
k = ch - '0';
}
Example: "12[a]" would give wrong result!
// ✓ CORRECT - Build multi-digit number
if (Character.isDigit(ch)) {
k = k * 10 + (ch - '0');
}
Mistake 2: Not resetting k after '['
// ❌ WRONG - k carries over!
else if (ch == '[') {
countStack.push(k);
stringStack.push(currentString);
currentString = "";
// Missing: k = 0
}
Example: "3[a]2[b]"
After first [: k=3
See '2': k=3*10+2=32 instead of 2 ✗
// ✓ CORRECT
else if (ch == '[') {
countStack.push(k);
stringStack.push(currentString);
currentString = "";
k = 0; // Reset!
}
Mistake 3: Wrong order when merging
// ❌ WRONG - Repeats prefix instead of current!
StringBuilder decoded = new StringBuilder();
for (int i = 0; i < count; i++) {
decoded.append(stringStack.peek());
}
// ✓ CORRECT - Repeat current, append to prefix
StringBuilder decoded = new StringBuilder(stringStack.pop());
for (int i = 0; i < count; i++) {
decoded.append(currentString);
}
Mistake 4: Using String instead of StringBuilder
// ❌ INEFFICIENT - Creates new string each time
String decoded = stringStack.pop();
for (int i = 0; i < count; i++) {
decoded += currentString; // O(n) each iteration!
}
// ✓ EFFICIENT - StringBuilder
StringBuilder decoded = new StringBuilder(stringStack.pop());
for (int i = 0; i < count; i++) {
decoded.append(currentString); // O(1) amortized
}
Mistake 5: Not handling prefix correctly
// ❌ WRONG - Loses "abc" prefix!
Input: "abc3[cd]"
After 'c': current = "c"
After 'd': current = "cd"
After ']': repeat "cd" 3 times = "cdcdcd"
Result: "cdcdcd" ✗ (missing "abc"!)
// ✓ CORRECT - Keep accumulating in current
Letters before '[' go into currentString
They're preserved when pushing to stringStack
🎯 Pattern Recognition
Problem Type: String Encoding/Nested Structures
Core Pattern: Stack Pattern 8 - Nested Processing
When to Apply:
✓ Nested structures (brackets, tags)
✓ Recursive patterns
✓ Encoding/decoding
✓ Expression parsing
Recognition Keywords:
- "decode"
- "encoded string"
- "k[...]" pattern
- "nested"
- "brackets"
- "repeat"
Similar Problems:
- Number of Atoms (LC 726) - Parse chemical formulas
- Ternary Expression Parser (LC 439)
- Remove Duplicate Letters (LC 316)
- Parsing A Boolean Expression (LC 1106)
Key Components:
┌────────────────────────────────────────────┐
│ Two stacks: count + string │
│ Track: repeat count and prefix string │
│ '[': Push state, start new level │
│ ']': Pop state, repeat, merge │
│ Digit: Build multi-digit number │
│ Letter: Append to current │
│ Time: O(maxK × n), Space: O(n) │
└────────────────────────────────────────────┘
🧠 Interview Strategy
Step 1: "This is nested structure decoding"
Step 2: "I'll use two stacks to track state"
Step 3: "Process character by character"
Key Points to Mention:
- Two stacks: one for counts, one for strings
- '[' means enter new level (push state)
- ']' means exit level (pop, repeat, merge)
- Handle multi-digit numbers (k = k*10 + digit)
- Current string tracks what's being built
- Reset k after using it
Walk Through Example:
"For '3[a2[c]]':
'3': k=3
'[': Push 3 and '', reset
'a': current='a'
'2': k=2
'[': Push 2 and 'a', reset
'c': current='c'
']': Pop 2,'a', repeat 'c' 2x, merge: 'acc'
']': Pop 3,'', repeat 'acc' 3x: 'accaccacc'"
Why Stack:
"Brackets create nesting. Stack's LIFO nature
perfectly matches bracket nesting - innermost
bracket processed first (most recent push)."
Complexity:
"Time: O(maxK × n) where maxK is largest repeat
count. In worst case, repeat entire string.
Space: O(n) for stacks storing intermediate states."
Edge Cases to Mention:
✓ Multi-digit numbers (12, 100)
✓ Nested patterns (3[a2[c]])
✓ Prefix/suffix strings (abc3[d]ef)
✓ No encoding blocks (abcdef)
📝 Quick Revision Notes
🎯 Core Concept:
Decode String: Use two stacks (count + string). Digit → build k. '[' → push k and current to stacks, reset. ']' → pop count/string, repeat current k times, merge with popped string. Letter → append to current.
⚡ Quick Implementation:
import java.util.Stack;
class Solution {
public String decodeString(String s) {
// Create 2 stacks: one for storing numbers and other for strings
Stack<Integer> repeatCounts = new Stack<>();
Stack<StringBuilder> prevContextString = new Stack<>();
int k = 0; // this is for handling 2 digit numbers.
StringBuilder currentContextString = new StringBuilder(""); // this is what comes inside []
for(char ch : s.toCharArray()) {
if(Character.isDigit(ch)) {
// This logic is to handle 2 digit numbers.
// For example: 23[c]. We need to create 23 as we read character by character.
k = (10 * k) + (ch - '0');
} else if (ch == '[') {
// new context is starting. Push the old context to stack and build the current context.
// In "3[a2[c]]", when 2nd [ comes, push the current context ("a") to the stack and the
// current number 2 also to the stack. Now, we have to build new context for "c"
prevContextString.push(currentContextString);
repeatCounts.push(k);
// Reset these 2 variables post stack push for new context.
currentContextString = new StringBuilder();
k = 0;
} else if (ch == ']') {
// Pop the both stacks.
// In "3[a2[c]]", when 1st ] comes, on top of the stack, we have "a" and "2".
// Seeing this, what we understood is, I have to repeat the current context "c", "2" number
// of times and pre-append with "a". So, it becomes, "acc". Now, make this as curent context string.
// Assign that string to result.
int repeat = repeatCounts.pop(); // to repeat the currentContextString
String prevContext = prevContextString.pop().toString();
StringBuilder temp = new StringBuilder(prevContext);
for(int i = 0; i < repeat; i++) {
temp.append(currentContextString);
}
// set the current context string for the next ].
currentContextString = temp;
} else {
currentContextString.append(ch);
}
}
return currentContextString.toString();
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.decodeString("3[a]2[bc]").equals("aaabcbc"));
System.out.println(s.decodeString("3[a2[c]]").equals("accaccacc"));
System.out.println(s.decodeString("2[abc]3[cd]ef").equals("abcabccdcdcdef"));
}
}
🔑 Key Insights:
- Pattern: Stack Pattern 8 (Nested Processing)
- Two stacks: Count + String (track state)
- Multi-digit: k = k*10 + digit
- '[' action: Push k and current, reset both
- ']' action: Pop, repeat, merge
- Time: O(maxK × n), Space: O(n) ✓
🎪 Memory Aid:
"Push state on '[', pop-repeat-merge on ']'!"
"Digit builds k, bracket manages state!" ✨
⚠️ Critical Steps:
Four character types:
1. Digit: k = k*10 + (ch-'0')
Build multi-digit number
2. '[': Push k and current, reset
Enter new nesting level
3. ']': Pop count/string, repeat, merge
Exit nesting level
4. Letter: current += ch
Regular character
🧪 Edge Cases
Case 1: Simple repeat
Input: "3[a]"
Output: "aaa"
No nesting
Case 2: Multi-digit number
Input: "12[a]"
Output: "aaaaaaaaaaaa"
12 times, not 1 then 2
Case 3: Nested pattern
Input: "3[a2[c]]"
Output: "accaccacc"
Inner decoded first
Case 4: Multiple blocks
Input: "3[a]2[bc]"
Output: "aaabcbc"
Sequential decoding
Case 5: Prefix and suffix
Input: "abc3[cd]xyz"
Output: "abccdcdcdxyz"
Preserve non-encoded parts
Case 6: Deep nesting
Input: "2[a2[b2[c]]]"
Output: "abccbccabccbcc"
Multiple nesting levels
All handled correctly! ✓
🎓 Complexity Analysis
Time Complexity: O(maxK × n)
Where:
n = length of input string
maxK = maximum value of repeat count
Worst case:
"300[a]" → repeat 'a' 300 times
Must create string of length 300
Nested case:
"10[10[a]]" → 10 × 10 = 100 repetitions
Can multiply across nesting levels
Overall: O(maxK × n) where maxK considers
product of nested repeat counts
Space Complexity: O(n)
Stack space:
countStack: O(d) where d = max nesting depth
stringStack: O(d)
Current string: O(result length)
Worst case: O(maxK × n)
Total: O(n + d)
Typically O(n) since d << n
For deeply nested: O(maxK × n)
🔄 Variations & Extensions
Extension 1: Return Decoded Length Only
// Don't build string, just calculate length
public int decodedLength(String s) {
Stack<Integer> countStack = new Stack<>();
Stack<Integer> lengthStack = new Stack<>();
int currentLength = 0;
int k = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
k = k * 10 + (ch - '0');
} else if (ch == '[') {
countStack.push(k);
lengthStack.push(currentLength);
currentLength = 0;
k = 0;
} else if (ch == ']') {
int prevLength = lengthStack.pop();
int repeatCount = countStack.pop();
currentLength = prevLength + currentLength * repeatCount;
} else {
currentLength++;
}
}
return currentLength;
}
Extension 2: Validate Encoded String
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
int k = 0;
for (char ch : s.toCharArray()) {
if (Character.isDigit(ch)) {
k = k * 10 + (ch - '0');
} else if (ch == '[') {
if (k == 0) return false; // Need count before [
stack.push(ch);
k = 0;
} else if (ch == ']') {
if (stack.isEmpty()) return false;
stack.pop();
}
}
return stack.isEmpty() && k == 0;
}
📚 Related Problems
Same Pattern: - Number of Atoms (LC 726) - Parse chemical formulas - Ternary Expression Parser (LC 439) - Basic Calculator III (LC 772)
Bracket Processing: - Valid Parentheses (LC 20) - Remove Invalid Parentheses (LC 301) - Minimum Remove to Make Valid (LC 1249)
Nested Structures: - Flatten Nested List Iterator (LC 341) - Mini Parser (LC 385)
Happy practicing! 🎯
Note: This problem teaches Stack Pattern 8: Nested Processing! Master this and you understand: (1) bracket matching and nesting, (2) state management across levels, (3) multi-digit number parsing, (4) recursive structure handling. This pattern is fundamental for parsers, compilers, and expression evaluation. Very common at Amazon, Meta, Google! 💪✨