Decode String — Solution

Problem

Given an encoded string where a number followed by a bracketed segment means "repeat that segment that many times", decode the full string. Brackets can be nested, so the encoding can be compactly recursive.

• Input: s = "3[a2[c]]"
• Output: "accaccacc"
• Explanation: 2[c] decodes to "cc", so a2[c] becomes "acc", then 3[acc] gives "accaccacc".

Counter-example: "2[ab]3[cd]" → "ababcdcdcd" — segments are independent when not nested.

Intuition

At every [ we're about to enter a new segment whose result we'll repeat. We need to remember what came before that bracket so we can prepend it after decoding. A stack lets us save and restore that "outer context" at each nesting level: push the state going in, pop and merge coming out.

Solution — Stack

Walk the string character by character, maintaining a running string and a running number. When we hit [, freeze the current state onto the stack and reset; when we hit ], thaw the previous state and concatenate the just-decoded segment repeated by its count.

1. Initialize an empty stack, current_string = "", and current_number = 0.
2. For each character c:
   • If c is a digit, update current_number = current_number * 10 + digit(c) to handle multi-digit counts.
   • If c is [, push (current_string, current_number) onto the stack, then reset both to empty/zero — we're entering a new scope.
   • If c is ], pop (prev_string, repeat_count) from the stack; the new current is prev_string + current_string * repeat_count.
   • Otherwise, append c to current_string.
3. Return current_string.

1def decodeString(self, s: str) -> str:
2    stack = []
3    current_string = ""
4    current_number = 0
5
6    for char in s:
7        if char.isdigit():
8            current_number = current_number * 10 + int(char)  # multi-digit numbers
9        elif char == '[':
10            stack.append((current_string, current_number))  # save outer context
11            current_string = ""
12            current_number = 0
13        elif char == ']':
14            prev_string, repeat_count = stack.pop()
15            current_string = prev_string + current_string * repeat_count  # prev comes first
16        else:
17            current_string += char
18
19    return current_string

Time: O(L) where L is the length of the decoded output — each character is written exactly once.

Space: O(n + d) where n is the input length (strings saved on the stack) and d is the maximum nesting depth (stack frames).

Complexity Summary

Common Mistakes

• Treating numbers as single-digit only — "12[ab]" has a two-digit multiplier; always use current_number * 10 + digit to accumulate.
• Pushing the wrong thing onto the stack — you push the state before the bracket (the string accumulated so far and the count for this bracket), not the state inside it.
• Reversing the concatenation order — it's prev_string + current_string * count, not the other way around; the outer prefix must come first.
• Forgetting to reset current_number to 0 after pushing — without the reset, the next bracket's count will accumulate on top of the old one.
• Off-by-one on when to read the number — the number always appears before its [, so finalize and push the count at the [, not before.

Related Problems

• Valid Parentheses — same push/pop bracket logic, simpler payload
• Longest Valid Parentheses — stack tracking indices of unmatched brackets
• Evaluate Reverse Polish Notation — stack that reduces tokens rather than expanding them
• Asteroid Collision — stack where popping resolves a condition between top and current element
• Minimum Add to Make Parentheses Valid — tracking unmatched bracket counts with a stack-equivalent counter