Decode String (LeetCode 394)
You get a string s written in a compact code: k[text] means text written out k times in a row, and text may itself contain more codes, so brackets can sit inside brackets. Expand every code and return the resulting plain string.
Every input keeps a few promises: s is always a correctly formed code, with no stray spaces and a ] for every [; each k is a positive whole number; and digits only ever appear as repeat counts, so the decoded text has no digits of its own (you will never see something like 3a or 2[4]). The inputs are also chosen so that the decoded string is at most 105 characters long.
Worked Examples
s = "3[a]2[bc]""aaabcbc"3[a] gives aaa and 2[bc] gives bcbc; written one after the other they make aaabcbc.s = "3[a2[c]]""accaccacc"2[c] becomes cc, so the outer bracket holds acc, and three copies of acc make accaccacc.s = "2[abc]3[cd]ef""abcabccdcdcdef"abc twice, then cd three times, then the plain letters ef at the end.⚖️Formal Constraints & Bounds
1 <= s.length <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.All the integers in
sare in the range[1, 300].
Core Insight
Brackets close in the reverse order they open, so a stack of saved (cur, num) pairs always has the context of the bracket being closed on top: push it at [, pop it and fold the inner text back in at ].
Real-World Scenario & Production Applications
Anything that nests needs this bookkeeping: a JSON or XML parser returning to the parent object when a child closes, a template engine expanding a loop inside a loop, a compiler checking that blocks close in the order they opened. Each open level saves where the outer level was, and closing the level resumes exactly there.
Step-by-Step Execution Trace Table
Example 2, s = "3[a2[c]]" (the trap case):
ch | Branch | What the code does | stack after | cur | num |
|---|---|---|---|---|---|
3 | digit | num = 0 * 10 + 3 | [] | "" | 3 |
[ | open | push ("", 3), then reset | [("", 3)] | "" | 0 |
a | letter | cur += "a" | [("", 3)] | "a" | 0 |
2 | digit | num = 0 * 10 + 2 | [("", 3)] | "a" | 2 |
[ | open | push ("a", 2), then reset: cur must not keep "a" | [("", 3), ("a", 2)] | "" | 0 |
c | letter | cur += "c" | [("", 3), ("a", 2)] | "c" | 0 |
] | close | pop ("a", 2): cur = "a" + "c" * 2 | [("", 3)] | "acc" | 0 |
] | close | pop ("", 3): cur = "" + "acc" * 3 | [] | "accaccacc" | 0 |
The loop ends and return cur gives "accaccacc".
| 1 | A `[` opens a smaller problem inside the current one, and the outer text has to wait for it: save the outer state before you go in, and restore it when the bracket closes. |
| 2 | `stack` holds one saved `(cur, num)` per `[` still open, innermost on top: brackets close in reverse order, so the top is always the context the next `]` needs. |
| 3 | Loop `for ch in s` with four branches: a digit extends `num`, `[` pushes, `]` pops and folds with `cur = prev + cur * k`, a letter does `cur += ch`; `return cur` at the end. |
| 4 | The trap: right after `stack.append((cur, num))`, reset `cur, num = "", 0`, or the outer text is repeated inside the bracket and the next count's digits are glued onto the old one. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Brackets inside brackets look like they need recursion: decode the inside first, then come back out. The Nesting Stack does the same work in one loop. A [ starts a smaller problem inside the current one, so the outer text and its repeat count are put aside on stack, and the inner text starts empty. A ] finishes the most recent [, so the pair on top of stack is exactly the one to come back to: pop it, and put the inner text back in, k times, after the outer text.
📞 The Analogy: Calls on Hold
You are on a phone call when a second call comes in. You put the first caller on hold, noting where you were, and answer the new one. A third call arrives, so the second goes on hold too. When a call ends, you always go back to the caller you put on hold most recently, and carry on exactly where you left off. The hold list is stack, the current call is cur, and hanging up is ]. The one thing you must never do is carry the old conversation into the new call: after putting a caller on hold, you start the new call fresh.
🔑 Why It Works
Brackets close in the reverse order they open, so the top of stack always belongs to the bracket being closed; everything below it waits untouched for its own ]. The reset right after the push is what keeps the levels apart: without cur, num = "", 0 the outer text would be repeated inside the bracket.
Not resetting after the push:
stack.append((cur, num))must be followed bycur, num = "", 0. Keepcurand"3[a2[c]]"returns"aacacaacacaacac"; keepnumand the inner count is read as32.Reading only one digit:
num = int(ch)keeps only the last digit of a count, so"10[a]"repeatsazero times. Usenum = num * 10 + int(ch).Folding in the wrong order: the saved text came before the
[, so it goes first:cur = prev + cur * k, notcur * k + prev("a2[c]"is"acc", not"cca").One saved context instead of a stack: a single saved text works for one level only; a bracket inside a bracket overwrites it and the outer text is lost. One saved pair per open
[is whatstackgives.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"k[text] repeats text k times" and brackets that can sit inside brackets: an inner part has to be decoded completely before the text around it can continue. Nesting where the last bracket opened is the first one closed is the signal for the Nesting Stack.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule, one character at a time: at [, stack.append((cur, num)), then cur, num = "", 0; at ], prev, k = stack.pop(), then cur = prev + cur * k; a digit extends num, a letter extends cur.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
num = num * 10 + int(ch), notnum = int(ch): counts go up to 300, so"10[a]"must repeat 10 times, not 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Nesting Stack. Each bracket is a smaller problem inside the current one, and the outer text has to wait until it is finished. So I keep cur, the text of the innermost open bracket, and num, the count I'm reading. I scan once. A digit extends num: times ten plus the digit, so counts like twelve work. A letter goes onto cur. At an open bracket I push the pair cur and num onto the stack, then reset both, so the inner text starts empty. Forgetting that reset is the classic bug: the outer text would be repeated inside. At a close bracket I pop the saved text and count, and set cur to the saved text plus cur repeated k times. Brackets close in reverse order, so the top of the stack is always the one I need. Time is O(N times L), where L is the output length, and space is O(N plus L).
Complexity & Mathematical Proof
O(N * L)
Look at the code: for ch in s runs N times. A digit costs O(1), and a [ pushes one pair and resets two variables, also O(1). A letter runs cur += ch, which may copy cur, and a ] builds prev + cur * k, a new string. Both results are pieces of the decoded string, so each is at most L characters, and each such step costs at most O(L). Total: at most N steps of O(L), so O(N * L).
O(N + L)
stack holds at most one pair per [, so at most N pairs. Their saved texts are different pieces of the decoded string that do not overlap (each is the text before a different open [), so together with cur they hold at most L characters. Space: O(N + L), and the returned string is L of it.
T(N, L) = N · O(L) = O(N · L)
Derivation Progression
O(1)
stack = [], cur = "" and num = 0 are three assignments.
N iterations
for ch in s reads each character once.
[O(1) per character
num = num * 10 + int(ch), or one push of (cur, num) and the reset cur, num = "", 0.
]O(L) per character at most
cur += ch and cur = prev + cur * k each build a string that is part of the decoded string, so at most L characters.
O(N · L)
At most N steps, each at most O(L).
Variable Definitions
Length of the input, len(s) (at most 30)
Length of the decoded string (at most 10^5)
A repeat count popped at ] (1 to 300)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N + L): at most N saved pairs whose texts, with cur, total at most L characters
O(L): the decoded string
Boundary Best / Worst Cases
: one bracket with nothing before it, such as 300[z]: only the final prev + cur * k builds a long string
Between the two; at LeetCode's limits (N <= 30, L <= 10^5) it is at most about 3 · 10^6 character copies
: a long text rebuilt at many ], such as 100[a]1[b]1[c]1[d]1[e]1[f]: every later ] copies the long prev again
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "k[text] means text written k times", "brackets can sit inside brackets". An inner part must be finished before the text around it can continue, and the last bracket opened is the first one closed: a Nesting Stack of saved (cur, num) pairs.
input characters but up to output characters, so the cost is in building the output, not in reading s. Each step builds at most characters: time at worst, about character copies at these limits, and space.
At scale the danger is the output, not the input: 26 characters, 10[10[10[10[abcdefghij]]]], decode to , so a decoder that accepts untrusted input checks the decoded size before it builds it. A recursive decoder uses the call stack as its stack; the explicit stack keeps deep nesting from overflowing it.
Core Algorithmic State Invariants
- Valid Input Is What Makes
popSafe
LeetCode promises a valid string, so every ] finds a saved pair and stack is empty at the end. A decoder for untrusted text checks stack before stack.pop() and after the loop, and rejects the input instead of crashing.
- Letters After
]Need No Special Case
After ], cur is the outer text again with the decoded bracket folded in, so a letter that follows, as in "2[a]b", simply goes onto cur and lands at the right level: "aab".
Decode String (LeetCode 394)
You get a string s written in a compact code: k[text] means text written out k times in a row, and text may itself contain more codes, so brackets can sit inside brackets. Expand every code and return the resulting plain string.
Every input keeps a few promises: s is always a correctly formed code, with no stray spaces and a ] for every [; each k is a positive whole number; and digits only ever appear as repeat counts, so the decoded text has no digits of its own (you will never see something like 3a or 2[4]). The inputs are also chosen so that the decoded string is at most 105 characters long.
Worked Examples
s = "3[a]2[bc]""aaabcbc"3[a] gives aaa and 2[bc] gives bcbc; written one after the other they make aaabcbc.s = "3[a2[c]]""accaccacc"2[c] becomes cc, so the outer bracket holds acc, and three copies of acc make accaccacc.s = "2[abc]3[cd]ef""abcabccdcdcdef"abc twice, then cd three times, then the plain letters ef at the end.⚖️Formal Constraints & Bounds
1 <= s.length <= 30sconsists of lowercase English letters, digits, and square brackets'[]'.sis guaranteed to be a valid input.All the integers in
sare in the range[1, 300].
Core Insight
Brackets close in the reverse order they open, so a stack of saved (cur, num) pairs always has the context of the bracket being closed on top: push it at [, pop it and fold the inner text back in at ].
Real-World Scenario & Production Applications
Anything that nests needs this bookkeeping: a JSON or XML parser returning to the parent object when a child closes, a template engine expanding a loop inside a loop, a compiler checking that blocks close in the order they opened. Each open level saves where the outer level was, and closing the level resumes exactly there.
Step-by-Step Execution Trace Table
Example 2, s = "3[a2[c]]" (the trap case):
ch | Branch | What the code does | stack after | cur | num |
|---|---|---|---|---|---|
3 | digit | num = 0 * 10 + 3 | [] | "" | 3 |
[ | open | push ("", 3), then reset | [("", 3)] | "" | 0 |
a | letter | cur += "a" | [("", 3)] | "a" | 0 |
2 | digit | num = 0 * 10 + 2 | [("", 3)] | "a" | 2 |
[ | open | push ("a", 2), then reset: cur must not keep "a" | [("", 3), ("a", 2)] | "" | 0 |
c | letter | cur += "c" | [("", 3), ("a", 2)] | "c" | 0 |
] | close | pop ("a", 2): cur = "a" + "c" * 2 | [("", 3)] | "acc" | 0 |
] | close | pop ("", 3): cur = "" + "acc" * 3 | [] | "accaccacc" | 0 |
The loop ends and return cur gives "accaccacc".
| 1 | A `[` opens a smaller problem inside the current one, and the outer text has to wait for it: save the outer state before you go in, and restore it when the bracket closes. |
| 2 | `stack` holds one saved `(cur, num)` per `[` still open, innermost on top: brackets close in reverse order, so the top is always the context the next `]` needs. |
| 3 | Loop `for ch in s` with four branches: a digit extends `num`, `[` pushes, `]` pops and folds with `cur = prev + cur * k`, a letter does `cur += ch`; `return cur` at the end. |
| 4 | The trap: right after `stack.append((cur, num))`, reset `cur, num = "", 0`, or the outer text is repeated inside the bracket and the next count's digits are glued onto the old one. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Brackets inside brackets look like they need recursion: decode the inside first, then come back out. The Nesting Stack does the same work in one loop. A [ starts a smaller problem inside the current one, so the outer text and its repeat count are put aside on stack, and the inner text starts empty. A ] finishes the most recent [, so the pair on top of stack is exactly the one to come back to: pop it, and put the inner text back in, k times, after the outer text.
📞 The Analogy: Calls on Hold
You are on a phone call when a second call comes in. You put the first caller on hold, noting where you were, and answer the new one. A third call arrives, so the second goes on hold too. When a call ends, you always go back to the caller you put on hold most recently, and carry on exactly where you left off. The hold list is stack, the current call is cur, and hanging up is ]. The one thing you must never do is carry the old conversation into the new call: after putting a caller on hold, you start the new call fresh.
🔑 Why It Works
Brackets close in the reverse order they open, so the top of stack always belongs to the bracket being closed; everything below it waits untouched for its own ]. The reset right after the push is what keeps the levels apart: without cur, num = "", 0 the outer text would be repeated inside the bracket.
Not resetting after the push:
stack.append((cur, num))must be followed bycur, num = "", 0. Keepcurand"3[a2[c]]"returns"aacacaacacaacac"; keepnumand the inner count is read as32.Reading only one digit:
num = int(ch)keeps only the last digit of a count, so"10[a]"repeatsazero times. Usenum = num * 10 + int(ch).Folding in the wrong order: the saved text came before the
[, so it goes first:cur = prev + cur * k, notcur * k + prev("a2[c]"is"acc", not"cca").One saved context instead of a stack: a single saved text works for one level only; a bracket inside a bracket overwrites it and the outer text is lost. One saved pair per open
[is whatstackgives.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"k[text] repeats text k times" and brackets that can sit inside brackets: an inner part has to be decoded completely before the text around it can continue. Nesting where the last bracket opened is the first one closed is the signal for the Nesting Stack.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision rule, one character at a time: at [, stack.append((cur, num)), then cur, num = "", 0; at ], prev, k = stack.pop(), then cur = prev + cur * k; a digit extends num, a letter extends cur.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
num = num * 10 + int(ch), notnum = int(ch): counts go up to 300, so"10[a]"must repeat 10 times, not 0.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use a Nesting Stack. Each bracket is a smaller problem inside the current one, and the outer text has to wait until it is finished. So I keep cur, the text of the innermost open bracket, and num, the count I'm reading. I scan once. A digit extends num: times ten plus the digit, so counts like twelve work. A letter goes onto cur. At an open bracket I push the pair cur and num onto the stack, then reset both, so the inner text starts empty. Forgetting that reset is the classic bug: the outer text would be repeated inside. At a close bracket I pop the saved text and count, and set cur to the saved text plus cur repeated k times. Brackets close in reverse order, so the top of the stack is always the one I need. Time is O(N times L), where L is the output length, and space is O(N plus L).
Complexity & Mathematical Proof
O(N * L)
Look at the code: for ch in s runs N times. A digit costs O(1), and a [ pushes one pair and resets two variables, also O(1). A letter runs cur += ch, which may copy cur, and a ] builds prev + cur * k, a new string. Both results are pieces of the decoded string, so each is at most L characters, and each such step costs at most O(L). Total: at most N steps of O(L), so O(N * L).
O(N + L)
stack holds at most one pair per [, so at most N pairs. Their saved texts are different pieces of the decoded string that do not overlap (each is the text before a different open [), so together with cur they hold at most L characters. Space: O(N + L), and the returned string is L of it.
T(N, L) = N · O(L) = O(N · L)
Derivation Progression
O(1)
stack = [], cur = "" and num = 0 are three assignments.
N iterations
for ch in s reads each character once.
[O(1) per character
num = num * 10 + int(ch), or one push of (cur, num) and the reset cur, num = "", 0.
]O(L) per character at most
cur += ch and cur = prev + cur * k each build a string that is part of the decoded string, so at most L characters.
O(N · L)
At most N steps, each at most O(L).
Variable Definitions
Length of the input, len(s) (at most 30)
Length of the decoded string (at most 10^5)
A repeat count popped at ] (1 to 300)
Memory Architecture & Bounds
O(1) Iterative, no recursion
O(N + L): at most N saved pairs whose texts, with cur, total at most L characters
O(L): the decoded string
Boundary Best / Worst Cases
: one bracket with nothing before it, such as 300[z]: only the final prev + cur * k builds a long string
Between the two; at LeetCode's limits (N <= 30, L <= 10^5) it is at most about 3 · 10^6 character copies
: a long text rebuilt at many ], such as 100[a]1[b]1[c]1[d]1[e]1[f]: every later ] copies the long prev again
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "k[text] means text written k times", "brackets can sit inside brackets". An inner part must be finished before the text around it can continue, and the last bracket opened is the first one closed: a Nesting Stack of saved (cur, num) pairs.
input characters but up to output characters, so the cost is in building the output, not in reading s. Each step builds at most characters: time at worst, about character copies at these limits, and space.
At scale the danger is the output, not the input: 26 characters, 10[10[10[10[abcdefghij]]]], decode to , so a decoder that accepts untrusted input checks the decoded size before it builds it. A recursive decoder uses the call stack as its stack; the explicit stack keeps deep nesting from overflowing it.
Core Algorithmic State Invariants
- Valid Input Is What Makes
popSafe
LeetCode promises a valid string, so every ] finds a saved pair and stack is empty at the end. A decoder for untrusted text checks stack before stack.pop() and after the loop, and rejects the input instead of crashing.
- Letters After
]Need No Special Case
After ], cur is the outer text again with the decoded bracket folded in, so a letter that follows, as in "2[a]b", simply goes onto cur and lands at the right level: "aab".