394. Decode String
Medium · solved 2026-10-02 · Open on LeetCode
stackstringrecursion
Time O(output) · Space O(n)
How to get there
What to remember at a "["
One question leads to the whole solution: what still has to be remembered when the loop reaches a [?
1. Start from how the format is defined. An encoded string is letters mixed with groups k[...], and the inside of a group is itself an encoded string. That definition refers to itself, so decoding does too: decode(k[X]) = decode(X) repeated k times. That points straight at recursion: to decode a group, decode its inside first, then repeat it.
2. Reading left to right, the count comes before its contents. On 3[a2[c]] the loop reads 3[ but can’t know what to repeat until the matching ]. So the current work has to be paused, the inside done, then the paused work picked up again. Groups nest, so the inside can contain its own 2[, which pauses again.
3. Pausing and resuming in reverse order means a stack. The most recently paused group is always the next one to finish: in 3[a2[c]], the 2[ opened last and closes first. It’s the same signal as in 2390 and 735: the most recent unfinished thing is the one dealt with next.
4. What to save: whatever the inner work will overwrite. While decoding the inside, the loop reuses k and current, so their outer values would be lost. Those two are exactly what has to be saved, and nothing else; the loop already tracks its own position in s. So the push is (k, current), followed by a reset to start the inside fresh.
5. At ], finish the inside and resume the outside. current now holds the decoded inside. Pop the paused state, repeat, before, and combine: before + current * repeat. That result becomes current again, because the loop is back in the outer group and later letters keep appending to it. If another ] follows, the same step repeats one level up.
6. The stack is what recursion keeps for you. In the recursive version from step 1, each call has its own local count and text, and the call stack holds the paused calls. The explicit stack holds the same thing: each (k, current) tuple is one paused call’s local variables. Writing it as a loop makes that stack visible.
The reusable recipe: when a problem makes you pause work, handle something nested, then resume, use a stack. What to push is the state the nested part would overwrite.
Let the variables' meanings write the branches
The if/elif chain follows from two lists: the kinds of character the input can hold, and what each variable means at every moment.
The kinds of character. The constraints allow four: digits, [, ], and lowercase letters. Each means something different, so each gets one branch, with the letter as the else for whatever is left.
What each variable always means:
| Variable | Always means |
|---|---|
k |
the count being read, from the digits since the last bracket |
current |
the decoded text since the last unclosed [, or since the start |
stack |
one saved pair (repeat, before) per [ that hasn’t closed yet |
Each branch is the smallest change that keeps those meanings true:
| Character | What it means | What must change | Code |
|---|---|---|---|
| digit | one more digit of the count | append it to k |
k = k * 10 + int(token) |
[ |
a new group starts | it is unclosed, so save its pair; k and current must now describe the new group |
stack.append((k, current)), then k, current = 0, "" |
] |
the group ends | it is no longer unclosed, so pop its pair; current must describe the outer group again |
repeat, before = stack.pop(), then current = before + current * repeat |
| letter | one more character of output | current gains it |
current += token |
A branch that broke a meaning would hand the next branch wrong data: skip the reset of k at [, and 2[3[a]] reads its inner count as 23. The four kinds never overlap, so the order of the checks doesn’t matter.
The method carries to other problems: list the kinds of input, write down what each variable always means, then write the update that keeps every meaning true for each kind.
Alternatives compared
| Approach | Time | Space | How it works |
|---|---|---|---|
| Expand the innermost group, repeat | O(n · output) | O(output) | Find a k[letters] with no bracket inside, replace it with its expansion, and rescan until no bracket is left. |
Stack of (count, text) pairs (chosen) |
O(output) | O(n) | Push the count and the outside text at [, pop and attach the repeated group at ]. |
| Recursion | O(output) | O(n) | A function decodes until the next ] and calls itself at each [; the call stack holds what the explicit stack holds. |
| Two stacks | O(output) | O(n) | One stack for texts, one for counts, always pushed and popped together. |
Writing the output takes time proportional to its length, so no approach can do better than O(output). The stack and the recursion both reach that, up to one copy of each group’s text per nesting level, and nesting is shallow since s is at most 30 characters. The stack keeps everything in one loop; the recursion reads closer to the grammar k[...].
solution.py
class Solution:
def decodeString(self, s: str) -> str:
stack = []
current = ""
k = 0
for token in s:
if token.isdigit():
k = k * 10 + int(token)
elif token == "[":
stack.append((k, current))
k, current = 0, ""
elif token == "]":
repeat, before = stack.pop()
current = before + current * repeat
else:
current += token
return currentNotes
Write your approach, insights, and mistakes here. Any other file in this folder (e.g. solution.py, attempt-1.py) is rendered below as code.