📚 Table of Contents
📋 Problem Statement
Given an encoded string, decode it according to:
k[segment] means repeat segment exactly k times.
Nested encodings are allowed.
Examples
Example 1:
Input: "3[a]2[bc]"Output: "aaabcbc"
Example 2:
Input: "3[a2[c]]"Output: "accaccacc"
Example 3:
Input: "2[abc]3[cd]ef"Output: "abcabccdcdcdef"
Constraints
1 <= s.length <= 30sconsists of lowercase letters, digits, and brackets- Input is always valid (well-formed brackets and repeat counts)
🎯 Real-World Analogy
Nested Playlist Macros
Imagine a music macro language where 3[chorus] means play chorus three times.
If chorus itself includes a macro, you must finish that inner macro before expanding outer one.
Stack frames represent "where we were" before entering a bracket block: previous built string + repeat count.
💡 Key Insights
- Parsing is stateful: current string segment plus current repeat number.
- When you hit
[, push state and start a fresh inner segment. - When you hit
], pop state and expand inner segment. - Multi-digit counts need accumulation:
num = num * 10 + digit. - Stack naturally handles arbitrary nesting depth.
💻 Solution Approaches
Approach 1: Recursive Descent Parsing
Time: O(L) | Space: O(L) recursion/strings
Elegant and close to grammar, but stack-based iterative parsing is often clearer in interviews.
Approach 2: Explicit Stack Parser (Recommended)
Time: O(L) | Space: O(L)
Single pass through characters, using stacks to remember outer contexts.
Here L is output-sensitive total processed characters.
Python Implementation
def decode_string(s: str) -> str:
"""
Decode nested k[segment] patterns using stacks.
Time: O(L)
Space: O(L)
"""
count_stack = []
string_stack = []
current = []
number = 0
for ch in s:
if ch.isdigit():
number = number * 10 + int(ch)
elif ch == '[':
count_stack.append(number)
string_stack.append(current)
current = []
number = 0
elif ch == ']':
repeat = count_stack.pop()
prev = string_stack.pop()
expanded = current * repeat
current = prev + expanded
else:
current.append(ch)
return ''.join(current)
JavaScript Implementation
function decodeString(s) {
/**
* Decode nested k[segment] patterns using stacks.
*
* Time: O(L)
* Space: O(L)
*/
const countStack = [];
const stringStack = [];
let current = "";
let number = 0;
for (const ch of s) {
if (ch >= "0" && ch <= "9") {
number = number * 10 + Number(ch);
} else if (ch === "[") {
countStack.push(number);
stringStack.push(current);
current = "";
number = 0;
} else if (ch === "]") {
const repeat = countStack.pop();
const prev = stringStack.pop();
current = prev + current.repeat(repeat);
} else {
current += ch;
}
}
return current;
}
🔍 Step-by-Step Walkthrough
Trace s = "3[a2[c]]":
Read 3 -> number = 3
Read [ -> push count=3, push current="", reset current
Read a -> current = "a"
Read 2[ -> push count=2, push current="a", reset current
Read c, then ] -> expand to "cc", combine with prev "a" -> current="acc"
Read final ] -> repeat "acc" three times -> "accaccacc"
⚡ Complexity Analysis
Time Complexity: O(L)
- Each input char is processed once.
- Expansion work is proportional to produced output length.
- Total is linear in decoded output size plus input scan.
Space Complexity: O(L)
- Stacks store pending counts and partial strings.
- Decoded output itself dominates memory footprint.
🔧 Edge Cases
- Multi-digit counts like
12[a] - Nested patterns like
2[a3[b]] - Plain suffix after encoded blocks (
3[a]xyz) - Single character inputs without brackets
- Deep nesting where recursion could hit limits (stack parser stays iterative)
🧪 Test Cases
Python
def test_decode_string():
assert decode_string("3[a]2[bc]") == "aaabcbc"
assert decode_string("3[a2[c]]") == "accaccacc"
assert decode_string("2[abc]3[cd]ef") == "abcabccdcdcdef"
assert decode_string("10[a]") == "aaaaaaaaaa"
assert decode_string("abc") == "abc"
print("✅ all tests passed")
JavaScript
function testDecodeString() {
console.assert(decodeString("3[a]2[bc]") === "aaabcbc", "test 1");
console.assert(decodeString("3[a2[c]]") === "accaccacc", "test 2");
console.assert(
decodeString("2[abc]3[cd]ef") === "abcabccdcdcdef",
"test 3"
);
console.assert(decodeString("10[a]") === "aaaaaaaaaa", "test 4");
console.assert(decodeString("abc") === "abc", "test 5");
console.log("✅ all tests passed");
}
💼 Interview Tips
- Clarify grammar first: digits always precede bracket groups.
- Explicitly call out multi-digit repeat handling.
- Explain each stack's role: counts vs previous strings.
- Prefer iterative solution to avoid recursion-depth discussions.
- Mention output-sensitive complexity if interviewer asks about worst case.
🎓 Key Takeaways
- Decode String is a textbook case for stack-based nested parsing.
- Reset-and-restore state at brackets keeps the logic clean.
- Tracking counts and prefixes separately prevents fragile string surgery.