Decode String

35 min · decodeString()

A short instruction can unfold into a wall of text. The challenge is remembering which instruction owns which piece when those instructions nest.

You're given an encoded string s. An encoded group has the form k[encoded], where k is a positive integer and the text inside the brackets must be repeated k times. Groups may appear inside other groups. Lowercase letters outside brackets are copied as they are.

Decode the entire string and return the expanded result.

A few ground rules:

Every number is a repeat count followed immediately by [.
Brackets are balanced, and every encoded group is complete.
Repeat counts apply only to the group directly after them.
The result always fits within the output limit below.

Constraints

1 <= s.length <= 3_000
s contains only lowercase English letters, digits, [ and ].
Every number forms a repeat count k with 1 <= k <= 300.
Brackets are balanced, and the nesting depth is at most 10.
The decoded output length is at most 100_000.

Hints

Finish the innermost group first

A closing bracket tells you one complete piece is ready. Expand that piece before attaching it to the text that came before its opening bracket.

Follow the grammar

When a parser reaches [, it can decode the inner section by calling the same logic again. The matching ] returns that completed section to its caller.

Save two kinds of context

When [ arrives, save both the repeat count and the partial text built so far. Two stacks — one for counts and one for prefixes — let you restore both at ].

Follow-up

Could you calculate the decoded length without constructing the decoded string itself?

Visible cases

Examples

Example 1

ready

Input: s = "3[a]2[bc]"
Expected: "aaabcbc"
Why: repeat 'a' three times, then 'bc' twice

Example 2

ready

Input: s = "3[a2[c]]"
Expected: "accaccacc"
Why: decode the inner c-group before repeating the outer group

Example 3

ready

Input: s = "2[abc]3[cd]ef"
Expected: "abcabccdcdcdef"
Why: adjacent groups expand independently; trailing letters stay

Interview signal

Asked at

AmazonGoogleBloomberg

Recursive descent

Recursive descent is a parsing method where one function reads a grammar section and calls itself when it finds a nested section. Here, each call owns the text up to its matching ].

Read letters into the current section. When a repeat count appears, parse the number, step over [, recursively decode the inner section, then repeat that result.

def decode_string(s: str) -> str:
    index = 0
 
    def parse_section() -> str:
        nonlocal index
        pieces: list[str] = []
 
        while index < len(s) and s[index] != "]":
            if s[index].isalpha():
                pieces.append(s[index])
                index += 1
                continue
 
            repeat = 0
            while index < len(s) and s[index].isdigit():
                repeat = repeat * 10 + int(s[index])
                index += 1
 
            index += 1  # skip '['
            inner = parse_section()
            index += 1  # skip ']'
            pieces.append(inner * repeat)
 
        return "".join(pieces)
 
    return parse_section()

With nesting capped at 10, each input character and produced character is copied only a constant number of times.

Time O(n + m), where n is encoded length and m is decoded length. Space O(d + m) for recursion depth d and the output pieces.

Two stacks

You can store the same suspended context explicitly. While scanning:

digits build the current repeat count;
letters join the current section;
[ saves the repeat count and the prefix built before this group;
] repeats the finished group and attaches it to the saved prefix.

def decode_string(s: str) -> str:
    counts: list[int] = []
    prefixes: list[list[str]] = []
    current: list[str] = []
    repeat = 0
 
    for char in s:
        if char.isdigit():
            repeat = repeat * 10 + int(char)
        elif char == "[":
            counts.append(repeat)
            prefixes.append(current)
            current = []
            repeat = 0
        elif char == "]":
            group = "".join(current) * counts.pop()
            current = prefixes.pop()
            current.append(group)
        else:
            current.append(char)
 
    return "".join(current)

The count and prefix stacks always have the same height: each [ pushes one of each, and its matching ] pops one of each. That pairing is the core correctness invariant.

Time O(n + m) with the fixed depth cap. Space O(n + m) for saved prefixes, counts, and the decoded result.

Loading editor

Console

ready to run

Ready to run.

3 cases are queued.

Visible testcase

Case 1

Arguments · JSON arrays: string

Expected

"aaabcbc"

Run: visible + custom · Submit: full suite