Decode String: The Stack Pattern for Nested Expressions
The stack solution to LeetCode Decode String, explained step by step — expanding nested k[...] patterns in one pass with a worked walkthrough and JavaScript code.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Decode String looks like a string-manipulation puzzle and turns out to be a lesson in how a stack handles nesting. The encoding rule is simple — k[...] means "repeat the bracket contents k times" — but the brackets can nest inside each other to any depth, and that is exactly where naive approaches fall apart.
The trick is to recognize that every [ opens a new scope and every ] closes one, just like function calls or matching parentheses. Whenever you see structure that opens and closes and nests, a stack is almost always the answer. Learn the reframe here and you have the template for evaluating expressions, parsing calculators, and unwinding any bracketed grammar.
The problem
Given an encoded string s, return its decoded form. The encoding rule is k[encoded_string], meaning the encoded_string inside the brackets repeats exactly k times. k is a positive integer, and the brackets may be nested. Input digits only ever appear as repeat counts, never as literal output.
Input: s = "3[a2[c]]"
Output: "accaccacc"
// 2[c] -> "cc"
// a2[c] -> "acc"
// 3[a2[c]] -> "acc" repeated 3 times -> "accaccacc"Two details drive the solution:
kcan be multi-digit —"10[a]"means tenas, not oneathen zero. You have to accumulate digits, not read one at a time.- Brackets nest, so when you finish an inner group you have to remember the outer string you were building before you dove in.
The brute force baseline
The obvious approach expands the innermost bracket first, then repeats. Find a ], walk backward to its matching [, read the number in front of it, expand that group in place, and start over on the shortened string.
function decodeString(s) {
while (s.includes('[')) {
// find the first ']' and the matching '[' just before it
const close = s.indexOf(']');
let open = close;
while (s[open] !== '[') open--;
// read the digits sitting in front of that '['
let numStart = open - 1;
while (numStart >= 0 && s[numStart] >= '0' && s[numStart] <= '9') numStart--;
numStart++;
const k = Number(s.slice(numStart, open));
const inner = s.slice(open + 1, close);
s = s.slice(0, numStart) + inner.repeat(k) + s.slice(close + 1);
}
return s;
}This works, but every expansion rebuilds the entire string. Each .slice + .repeat copies characters proportional to the current length, and you do that once per bracket pair. On deeply nested or heavily repeated input the intermediate strings blow up and you recopy them again and again — quadratic in the worst case, and wasteful even when it isn't. You never need to rescan the whole string; you only need to remember where you left off.
The key insight: stack the outer context
Reframe the string as a walk through nested scopes. Keep two "current" trackers as you scan left to right:
currentStr— the string you are building in the scope you are currently inside.currentNum— the multiplier you are accumulating for the next[.
When you hit a [, you are about to enter a nested scope, and the outer currentStr and currentNum would be lost if you overwrote them. So push them onto a stack and reset both to empty. When you hit the matching ], that inner scope is done: pop the multiplier and the outer string back off, repeat the inner string, and stitch it onto the restored outer context.
The stack is what gives you unbounded nesting for free. Each [ parks one level of context; each ] restores it. You never rescan — one left-to-right pass does everything.
The optimal solution
This is the exact algorithm the Decode String visualizer steps through, with the same variable names:
var decodeString = function (s) {
let stack = [];
let currentNum = 0;
let currentStr = '';
for (let char of s) {
if (char >= '0' && char <= '9') {
currentNum = currentNum * 10 + Number(char);
} else if (char === '[') {
stack.push(currentStr);
stack.push(currentNum);
currentStr = '';
currentNum = 0;
} else if (char === ']') {
let num = stack.pop();
let prevStr = stack.pop();
currentStr = prevStr + currentStr.repeat(num);
} else {
currentStr += char;
}
}
return currentStr;
};Four branches, one per character type. Digits accumulate into currentNum with the * 10 + digit trick so multi-digit counts work. A [ pushes the outer string then the number and clears both trackers. A ] pops in reverse order — number first, then the previous string, matching the push order — and rebuilds currentStr. Any other character just appends to currentStr. Note the push/pop symmetry: string then number going in, number then string coming out.
Walkthrough
Tracing s = "3[a2[c]]". The stack is written bottom-to-top; each row shows the state after processing that character.
| char | branch | currentNum | currentStr | stack |
|---|---|---|---|---|
| — | init | 0 | "" | [] |
3 | digit | 3 | "" | [] |
[ | open | 0 | "" | ["", 3] |
a | char | 0 | "a" | ["", 3] |
2 | digit | 2 | "a" | ["", 3] |
[ | open | 0 | "" | ["", 3, "a", 2] |
c | char | 0 | "c" | ["", 3, "a", 2] |
] | close | 0 | "acc" | ["", 3] |
] | close | 0 | "accaccacc" | [] |
The two close steps are the payoff. At the first ], we pop num = 2 and prevStr = "a", then currentStr = "a" + "c".repeat(2) = "acc". At the second ], we pop num = 3 and prevStr = "", then currentStr = "" + "acc".repeat(3) = "accaccacc". The stack is empty, the scan is done, and currentStr is the answer.
Complexity
Let n be the input length and N the length of the final decoded output.
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (repeated expansion) | O(n · N) | O(N) | rebuilds the whole string once per bracket pair |
| Stack (one pass) | O(N) | O(N) | each output character is written exactly once; stack holds nested contexts |
The stack solution's time is dominated by producing the output — every character in the decoded result is copied once during a .repeat + concatenation, so the total work is proportional to N, the output size. Space is also O(N): the stack stores the partial outer strings, and their combined length is bounded by the output you are building toward.
Common mistakes
- Reading one digit as the whole count.
"12[a]"must accumulate1then2into12. UsingNumber(char)directly instead ofcurrentNum * 10 + Number(char)decodes it as twelve wrong characters. - Resetting only one tracker on
[. You must clear bothcurrentStrandcurrentNumwhen entering a scope. Forgetting to resetcurrentStrleaks the outer string into the inner group. - Popping in the wrong order. You push string then number, so you must pop number then string. Swap them and you multiply by a string and concatenate a number — silent garbage, not a crash.
- Concatenating in the wrong direction. It is
prevStr + currentStr.repeat(num), notcurrentStr.repeat(num) + prevStr. The outer context came first in the original text, so it goes first in the result. - Reaching for recursion without a base for depth. Recursion works too, but the stack version makes the nesting explicit and never risks a call-stack overflow on pathological input.
Where this pattern shows up next
The push-on-open, pop-on-close pattern is the backbone of every bracket-and-scope problem:
- Minimum Add to Make Parentheses Valid — the same open/close bookkeeping, counting unmatched brackets instead of expanding them.
- Reverse Words in a String — another parse-and-rebuild scan where you accumulate a token and flush it at a boundary.
- Count and Say — building an output string character-run by character-run, the same "accumulate then emit" rhythm.
- Sum of Beauty of All Substrings — string scanning with running counts, a cousin of the tracker-based approach here.
You can also step through Decode String interactively to watch the context stack grow on each [ and unwind on each ].
FAQ
Why does Decode String need a stack instead of a simple loop?
Because the brackets nest to arbitrary depth. When you enter an inner k[...], you have to remember the outer string and multiplier you were mid-way through building, and there can be many layers of "outer" at once. A stack stores each suspended context in the right order so that every ] restores exactly the scope its matching [ left behind. A flat pair of variables can only remember one level and would lose everything above it.
How do I handle multi-digit repeat counts like "100[a]"?
Accumulate the number across characters with currentNum = currentNum * 10 + Number(char) on every digit. When you read 1, 0, 0 in sequence, that builds 1, then 10, then 100, so the count is correct before you ever hit the [. Reading digits one at a time with Number(char) alone would treat 100 as three separate multipliers and produce the wrong output entirely.
What is the time and space complexity of the stack solution?
Both are O(N), where N is the length of the decoded output. The time is bounded by producing that output — each character is written once during the repeat-and-concatenate step at a closing bracket. The space is the stack plus the strings being built, whose combined length is bounded by the output size. Since the decoded string can be far longer than the input ("10[abc]" is 7 characters in, 30 out), N — not the input length — is what governs the cost.
Can Decode String be solved with recursion instead?
Yes. A recursive parser can call itself whenever it sees a [ and return when it sees the matching ], which mirrors the stack version because recursion uses the call stack for the same bookkeeping. The explicit-stack approach is usually preferred in interviews: it makes the saved context visible, avoids deep call-stack recursion on adversarial input, and maps one-to-one onto the single left-to-right scan.
Why push the string before the number when entering a bracket?
It sets up a clean symmetric pop. You push currentStr then currentNum, so the number sits on top of the stack. On the closing ], the first pop returns the number and the second returns the outer string — exactly the order you need to compute prevStr + currentStr.repeat(num). Keeping push and pop mirror-imaged is what makes the close branch a tidy two-line operation instead of index juggling.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.