Decode String

Problem

You get an encoded string that uses the rule k[segment]: the segment inside the square brackets is repeated exactly k times (k is a positive integer, always present before a [). Encodings can nest — a bracketed segment may itself contain more k[...] blocks. Plain lowercase letters outside any brackets are copied through unchanged, and digits appear only as repeat counts.

Return the fully decoded string. The input is guaranteed well-formed.

Examples

• "3[a]2[bc]" → "aaabcbc" — a three times, then bc twice.
• "3[a2[c]]" → "accaccacc" — inner 2[c] becomes cc, so the outer block repeats acc three times.
• "2[abc]3[cd]ef" → "abcabccdcdcdef" — two blocks, then a plain tail ef.

Constraints

• 1 <= s.length <= 30
• 1 <= k <= 300; the decoded output is guaranteed to fit (at most ~10^5 characters)
• s contains only lowercase letters, digits, and square brackets, and is always valid

The input is tiny, but nesting means the output can be large — the expected solution is a single left-to-right pass, linear in the output size.

Think about it first

TL;DR

One pass with a stack of (previous_string, repeat_count) frames — O(m) time and space, where m is the decoded output length.

Approach 1 — Brute force (expand innermost blocks repeatedly)

An innermost block k[letters] contains no nested brackets, so it can be expanded by plain text substitution. Do that repeatedly until no brackets remain.

import re


def decodeString(s: str) -> str:
    block = re.compile(r"(\d+)\[([a-z]*)\]")

    def expand(m: re.Match) -> str:
        count = int(m.group(1))
        return count * m.group(2)

    while "[" in s:
        s = block.sub(expand, s)
    return s

Complexity: O(d · m) time, where d is the nesting depth and m the output size — each sweep rebuilds the whole (growing) string once per nesting level; O(m) space.

It passes here because the input is at most 30 characters, but each level of nesting re-copies the entire partially decoded string. With counts up to 300, the intermediate strings are rebuilt in full, which the stack pass avoids. It also relies on the regex engine instead of showing the parsing skill being tested.

Approach 2 — Stack of suspended frames

Decoding is interrupted work. While building a segment, a [ forces you to shelve both the text built so far and the repeat count just read, then start a fresh segment; the matching ] resumes the most recently shelved frame. This last-in-first-out suspend/resume is a stack of (previous_string, count) pairs.

Each character drives one of four branches:

flowchart TD
    A[Read next char] --> B{What is it?}
    B -->|digit| C[num = num*10 + digit]
    B -->|letter| D[cur += letter]
    B -->|open bracket| E[push cur and num; reset cur and num]
    B -->|close bracket| F[pop prev and k; cur = prev + cur*k]
    C --> A
    D --> A
    E --> A
    F --> A

def decodeString(s: str) -> str:
    stack: list[tuple[str, int]] = []   # (string built before '[', its count)
    cur = ""
    num = 0
    for ch in s:
        if ch.isdigit():
            num = num * 10 + int(ch)    # counts can be multi-digit
        elif ch == "[":
            stack.append((cur, num))
            cur, num = "", 0
        elif ch == "]":
            prev, k = stack.pop()
            cur = prev + cur * k
        else:
            cur += ch
    return cur

Walkthrough on "3[a2[c]]":

Result: "accaccacc".

Complexity: O(m) time — every output character is written O(1) amortized times (string concatenation in a loop is acceptable at these sizes; use a list of parts to avoid repeated copying). O(m) space for the stack frames and result.

Approach 3 — Recursive descent

The grammar is recursive (segment → letters | k[segment] ...), so let the call stack be the stack. A helper consumes characters via a shared index and calls itself on each bracketed block, returning when it sees ]. This is a recursive descent parser: one function per grammar rule, consuming tokens left to right.

def decodeString(s: str) -> str:
    i = 0

    def parse() -> str:
        nonlocal i
        parts: list[str] = []
        num = 0
        while i < len(s):
            ch = s[i]
            i += 1
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == "[":
                parts.append(num * parse())   # recurse into the block
                num = 0
            elif ch == "]":
                break                         # this block is done
            else:
                parts.append(ch)
        return "".join(parts)

    return parse()

Walkthrough on "3[a2[c]]": the outer parse reads 3, sees [, and recurses. The inner call collects "a", reads 2, recurses again; the innermost call collects "c", hits ], returns "c", which becomes "cc". The middle call hits the next ] and returns "acc", which the outer call multiplies to "accaccacc".

Complexity: O(m) time, O(m) space (recursion depth = nesting depth, plus the output).

Common pitfalls

• Single-digit assumption: counts like 12[ab] need num = num * 10 + int(ch), not num = int(ch).
• Forgetting to reset cur and num after pushing on [ — the new block must start empty.
• Order of concatenation on ]: it’s prev + cur * k; writing cur * k + prev scrambles nested output.
• Multiplying too early: the count applies to the entire bracketed block, which you don’t know until ] — resist decoding at the [.

Pattern takeaway

When input has nested structure delimited by open/close markers, a stack holds the suspended outer context while you work on the inner one — push your partial state at every opener, pop and combine at every closer. The recursive version is the same idea with the call stack doing the bookkeeping; recognizing that equivalence (explicit stack ⇔ recursion) is the transferable skill for every parser-shaped interview problem.