Decode String (LeetCode 394)
You will see how one stack of saved contexts decodes brackets inside brackets in a single pass.
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"s = "3[a2[c]]""accaccacc"s = "2[abc]3[cd]ef""abcabccdcdcdef"⚖️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].
Why It Works & Core Invariant
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. |
Target: Decode String (LeetCode 394). An empty stack: no `[` is open yet, so there is nothing to come back to.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
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.
🪄 The Mathematical Harmony / Magic Trick
for ch in s: if ch.isdigit(): num = num * 10 + int(ch) elif ch == "[": stack.append((cur, num)) cur, num = "", 0 elif ch == "]": prev, k = stack.pop() cur = prev + cur * k else: cur += chreturn cur 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.
💡 Summary
Push (cur, num) at [ and reset both, pop and fold with cur = prev + cur * k at ], read counts digit by digit, and return cur once every bracket is closed. One pass over s: O(N * L) time at worst, O(N + L) space.
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
You will see how a senior engineer spots nesting in a problem statement and defends the stack of saved contexts out loud.
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
stack holds one saved (cur, num) for every [ still open, innermost on top, and cur is the text of the innermost open bracket read so far. At [: stack.append((cur, num)), then cur, num = "", 0. At ]: prev, k = stack.pop(), then cur = prev + cur * k.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
cur, num = "", 0right afterstack.append((cur, num)): without thecurreset,"3[a2[c]]"repeats the outerainside the bracket and returns"aacacaacacaacac"; without thenumreset the inner count is read as32.num = num * 10 + int(ch), notnum = int(ch): counts go up to 300, so"10[a]"must repeat 10 times, not 0.cur = prev + cur * k, notcur * k + prev: the saved text came before the[("a2[c]"is"acc", not"cca").
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).
So: push (cur, num) at [ and reset both, pop and fold at ], and say why the top of stack is always the right context.
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)
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).
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
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"k[text]meanstextwrittenk 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.
Reset cur, num = "", 0 right after the push. 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
`stack` holds one `(cur, num)` for every `[` still open, innermost on top. Brackets close in reverse order, so the top is always the context the next `]` needs.
At `[`, `stack.append((cur, num))` saves the outer text and the count, then `cur, num = "", 0` starts the inner text empty. Skipping the reset repeats the outer text inside the bracket.
`prev, k = stack.pop()` and `cur = prev + cur * k` put the finished inner text back after the outer text, `k` times. One pass over `s`, each step building at most L characters: O(N * L) time, O(N + L) space.
Decode String (LeetCode 394)
You will see how one stack of saved contexts decodes brackets inside brackets in a single pass.
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"s = "3[a2[c]]""accaccacc"s = "2[abc]3[cd]ef""abcabccdcdcdef"⚖️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].
Why It Works & Core Invariant
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. |
Target: Decode String (LeetCode 394). An empty stack: no `[` is open yet, so there is nothing to come back to.
Intervals sorted by start coordinate; monotonic stack preserves strictly increasing or decreasing element values.
Sweep: if curr.start <= prev.end: merge; Stack: while stack and nums[i] >= stack[-1]: stack.pop().
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.
🪄 The Mathematical Harmony / Magic Trick
for ch in s: if ch.isdigit(): num = num * 10 + int(ch) elif ch == "[": stack.append((cur, num)) cur, num = "", 0 elif ch == "]": prev, k = stack.pop() cur = prev + cur * k else: cur += chreturn cur 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.
💡 Summary
Push (cur, num) at [ and reset both, pop and fold with cur = prev + cur * k at ], read counts digit by digit, and return cur once every bracket is closed. One pass over s: O(N * L) time at worst, O(N + L) space.
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
You will see how a senior engineer spots nesting in a problem statement and defends the stack of saved contexts out loud.
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
stack holds one saved (cur, num) for every [ still open, innermost on top, and cur is the text of the innermost open bracket read so far. At [: stack.append((cur, num)), then cur, num = "", 0. At ]: prev, k = stack.pop(), then cur = prev + cur * k.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
cur, num = "", 0right afterstack.append((cur, num)): without thecurreset,"3[a2[c]]"repeats the outerainside the bracket and returns"aacacaacacaacac"; without thenumreset the inner count is read as32.num = num * 10 + int(ch), notnum = int(ch): counts go up to 300, so"10[a]"must repeat 10 times, not 0.cur = prev + cur * k, notcur * k + prev: the saved text came before the[("a2[c]"is"acc", not"cca").
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).
So: push (cur, num) at [ and reset both, pop and fold at ], and say why the top of stack is always the right context.
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)
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).
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
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"k[text]meanstextwrittenk 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.
Reset cur, num = "", 0 right after the push. 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
`stack` holds one `(cur, num)` for every `[` still open, innermost on top. Brackets close in reverse order, so the top is always the context the next `]` needs.
At `[`, `stack.append((cur, num))` saves the outer text and the count, then `cur, num = "", 0` starts the inner text empty. Skipping the reset repeats the outer text inside the bracket.
`prev, k = stack.pop()` and `cur = prev + cur * k` put the finished inner text back after the outer text, `k` times. One pass over `s`, each step building at most L characters: O(N * L) time, O(N + L) space.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Keep one saved context per open level | stack: list[tuple[str, int]] = [] | An empty stack: no `[` is open yet, so there is nothing to come back to. |
| The state of the innermost level | cur = ""
num = 0 | `cur` is the text being built at the innermost open level and `num` the count being read for the next `[`. |
| Read the input once, left to right | for ch in s: | Every character either extends the current level, opens a new one or closes it. |
| Build the count digit by digit | num = num * 10 + int(ch) | Counts go up to 300, so each new digit shifts the old ones left by one place. |
| Opener: save the outer state, then start the inner one empty | stack.append((cur, num))
cur, num = "", 0 | The outer text waits on `stack` with the count this bracket will use. Resetting both is the trap: the inner text must not start with the outer text in it. |
| Closer: restore the outer state and fold the finished inner result in | prev, k = stack.pop()
cur = prev + cur * k | The `]` closes the most recent `[`, whose saved pair is on top. The inner text goes back after the outer text, `k` times. |
| Plain content joins the innermost level | cur += ch | A letter belongs to whichever bracket is open right now. |
| Everything is closed: the outermost level holds the answer | return cur | A valid input closes every `[`, so `stack` is empty and `cur` is the whole decoded string. |