Problem overview
You get an encoded string s and return the string it stands for. The only rule is k[text]: the text inside the brackets is written out k times. Brackets can be nested, so the text inside a pair of brackets may itself contain encoded parts.
The input is always well-formed. Digits appear only as repeat counts, every count is followed by [, and the decoded output never exceeds 100,000 characters. Letters can also appear outside any brackets, as in "2[abc]3[cd]ef", where the trailing ef is copied as it is.
Take "3[a2[c]]". The inner part 2[c] decodes to cc, so the outer brackets hold acc. Repeating that three times gives "accaccacc". Notice the order: the innermost brackets must be finished before the outer repeat can happen.
Approach: one buffer per open bracket
That inside-out order is what a stack is for. Every [ opens a new context, and the matching ] closes the most recent one. While a context is open, you collect its letters. When it closes, you repeat what you collected and hand the result to the context one level out.
This solution uses a single Python list as the stack and stores two kinds of entries in it:
- count strings such as
"3"or"12", kept as text while the digits arrive; - text buffers, the decoded letters collected so far at one nesting level.
Because the input is valid, a count is always followed by [, which pushes a fresh buffer on top of it. So when a ] arrives, the top entry is the buffer to repeat and the entry just below it is its count. Here is the stack after each character of "3[a2[c]]":
| Character | Stack afterwards |
|---|---|
3 | ['3'] |
[ | ['3', ''] |
a | ['3', 'a'] |
2 | ['3', 'a', '2'] |
[ | ['3', 'a', '2', ''] |
c | ['3', 'a', '2', 'c'] |
] | ['3', 'acc'] |
] | ['accaccacc'] |
At the first ], the solution pops 'c' and '2', builds 'cc' and appends it to the buffer below, turning 'a' into 'acc'. At the second, it pops 'acc' and '3', and since nothing is left underneath, the repeated string becomes the only entry. A recursive decoder that calls itself at every [ works too, but the explicit stack keeps everything in one loop with no recursion to trace.
Step by step
- Create the stack. An empty list is enough;
appendpushes andpopremoves from the end. - Scan the input once. Every character falls into exactly one of four cases: an opening bracket, a letter, a digit or a closing bracket.
- Opening bracket. Push an empty string. This new buffer collects the text that will be repeated. Without it, the next letter would be glued onto the count below it, producing something like
"3a". - Letters, part one. If the stack is empty, push an empty buffer first. This only happens for letters before any bracket, as in
"ab3[c]", or at the very start of the string. - Letters, part two. Add the letter to the buffer on top of the stack.
- Digits, part one. Look at the top entry, using an empty string when the stack is empty, so the next check never reads past the end of the list.
- Digits, part two. If the top is not a count string, this digit starts a new count, so push it as its own entry. If the top is already a count, extend it. That second branch is what turns
1followed by2into the single count12. - Closing bracket, part one. Pop the buffer, then pop its count and convert it with
int(). The buffer was pushed last, so it comes off first. - Closing bracket, part two. Repeat the buffer. If the stack is now empty, push the result; otherwise append it to the buffer that is now on top, which belongs to the enclosing level.
- Return the top of the stack. For valid input, exactly one buffer remains when the loop ends, holding the whole decoded string.
The solution in Python
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for c in s:
if c == '[':
stack.append("")
elif c.isalpha():
if not stack:
stack.append("")
stack[-1] += c
elif c.isdigit():
top = stack[-1] if stack else ""
if not top.isnumeric():
stack.append(c)
else:
stack[-1] += c
else:
currStr = stack.pop()
currNum = int(stack.pop())
repeated = currStr * currNum
if not stack:
stack.append(repeated)
else:
stack[-1] += repeated
return stack[-1]
A few Python details carry this solution:
- String repetition.
currStr * currNumrepeats a string, so"ab" * 3is"ababab". The count must be anint; multiplying by the string"3"raises aTypeError, which is whyint()wraps the second pop. - Empty-string checks.
"".isnumeric()isFalse. That is exactly the behavior you want: a fresh, empty buffer is not a count, so a digit that follows[starts a new count instead of being glued onto the buffer. - Guarding
stack[-1]. Indexing an empty list raisesIndexError. The conditional expressionstack[-1] if stack else ""and theif not stackchecks avoid it; an empty list is falsy in Python. - Immutable strings.
stack[-1] += cdoes not change a string in place. It builds a new string and stores it back at the top of the list, which is fine here because the strings are short. - The final
else. It catches every character that is not[, a letter or a digit. With valid input, that can only be].
Complexity
Let n be the length of s and m the length of the decoded string.
Time: the loop runs n times. Each iteration builds at most two strings: an extended buffer, or a repetition plus a fold. None of them is longer than the final output, so the total work is at most O(n · m). Writing the output already costs O(m), so the real cost sits between those bounds, and with n ≤ 30 and m ≤ 10^5 it is small either way.
Space: O(n + m). The stack holds at most one entry per character of input, and the buffers on it together never hold more than the output.
Edge cases and common mistakes
- Multi-digit counts. Treating each digit as its own count breaks
"12[x]". The count must be built up digit by digit in one stack entry before it is converted. - Letters outside brackets.
"ab3[c]"needs a buffer before any bracket appears, and"2[a]bc"appendsbcto the buffer created by the first repeat. Both are handled by the lazy push in the letter branch. - A count right after
[. In"2[3[a]]", the3arrives while an empty buffer is on top. Pushing it as a new entry keeps the empty buffer in place, and the decodedaaais later folded into that buffer. - Popping in the wrong order. The buffer is on top and the count is under it. Swapping the two pops tries to convert letters with
int(). - Forgetting the fold. After a repeat, the result belongs to the enclosing level. Pushing it as a separate entry breaks the layout the closing branch relies on:
"3[a]2[bc]"would return only"bcbc", and in"3[a2[c]]"the outer bracket would pop'a'where it expects the count.
Testing
Try these in the editor above, along with the three examples from the statement:
"abc"returns"abc"(no brackets at all)."10[a]"returns"aaaaaaaaaa"(a two-digit count)."2[3[a]b]"returns"aaabaaab"(a letter after an inner group)."a2[b2[c]]d"returns"abccbccd"(text before, inside and after)."2[3[a]]"returns"aaaaaa"(a count directly after a bracket).
