Decode String (LeetCode 394) — Nested Bracket Decoding

Given an encoded string like 3[a2[c]], decode it to accaccacc. The encoding rule is k[encoded_string], where the encoded_string inside the brackets is repeated k times.

The Stack Approach

Use a stack to handle nesting. When you hit ], pop back to the matching [, build the substring, repeat it, and push the result back.

def decode_string(s):
    """
    Decode encoded string using a stack.
    Time: O(n * max_k), Space: O(n)
    where n is the decoded output length
    """
    stack = []
    current_num = 0
    current_str = ""

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            stack.append((current_str, current_num))
            current_str = ""
            current_num = 0
        elif char == ']':
            prev_str, num = stack.pop()
            current_str = prev_str + current_str * num
        else:
            current_str += char

    return current_str

Trace

Input: 3[a2[c]]

char | current_num | current_str | stack
-----|-------------|-------------|------
3    | 3           | ""          | []
[    | 0           | ""          | [("", 3)]
a    | 0           | "a"         | [("", 3)]
2    | 2           | "a"         | [("", 3)]
[    | 0           | ""          | [("", 3), ("a", 2)]
c    | 0           | "c"         | [("", 3), ("a", 2)]
]    | 0           | "acc"       | [("", 3)]         ← "a" + "c"*2
]    | 0           | "accaccacc" | []                 ← "" + "acc"*3

Output: accaccacc

Recursive Approach

def decode_string_recursive(s):
    """Recursive decoder using an index pointer."""
    def helper(s, i):
        result = ""
        while i < len(s) and s[i] != ']':
            if s[i].isdigit():
                num = 0
                while i < len(s) and s[i].isdigit():
                    num = num * 10 + int(s[i])
                    i += 1
                i += 1  # skip '['
                decoded, i = helper(s, i)
                i += 1  # skip ']'
                result += decoded * num
            else:
                result += s[i]
                i += 1
        return result, i

    return helper(s, 0)[0]

Edge Cases

• No encoding — "abc" returns "abc"
• Multi-digit numbers — "10[a]" returns "aaaaaaaaaa"
• Deeply nested — "2[a2[b3[c]]]" works correctly with stack
• Adjacent encodings — "2[a]3[b]" returns "aabbb"
• Empty brackets — "3[]" returns ""

Complexity

When to Use This Pattern

Whenever you have nested structures that need inside-out processing:

• Parsing nested expressions
• Expanding templates or macros
• Processing recursive grammars

Related Problems

• Number of Atoms (LeetCode 726) — similar nested parsing with counts
• Brace Expansion (LeetCode 1087)
• Basic Calculator (LeetCode 224) — nested expression evaluation
• Remove Outermost Parentheses (LeetCode 1021)