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


class Solution:
    def decodeString(self, 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.

Why the constraints kill it: here it actually passes (the input is only 30 chars), but each level of nesting re-copies the entire partially-decoded string, and with counts up to 300 the intermediate strings are rebuilt wholesale — pure wasted copying that the stack pass avoids. It also leans on the regex engine instead of demonstrating the parsing skill being tested.

Approach 2 — Stack of suspended frames

The insight: decoding is interrupted work. While building some segment, a [ forces you to shelve both the text built so far and the repeat count you just read, then start a fresh segment; the matching ] resumes exactly the most recently shelved frame. LIFO suspend/resume is a stack of (previous_string, count) pairs.

class Solution:
    def decodeString(self, 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 fine at these sizes; use a list-of-parts if paranoid). O(m) space for the stack frames and result.

Approach 3 — Recursive descent

The insight: 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 textbook recursive descent parser — one mutually recursive function per grammar rule, consuming tokens left to right.

class Solution:
    def decodeString(self, s: str) -> str:
        self.i = 0

        def parse() -> str:
            parts: list[str] = []
            num = 0
            while self.i < len(s):
                ch = s[self.i]
                self.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.