Decode String

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Expand a compressed string. In the input, k[text] means "text repeated k times", where k is a positive integer and can have several digits. Brackets can be nested, and plain letters can appear anywhere. The input is always well formed. Return the fully expanded string.

    A compact test of stack thinking: every [ opens a new level, and every ] closes the innermost one. Variants show up as "expand a template", "unzip a run-length format" or "evaluate nested repeats". Original problem: LeetCode 394.

    Example

    The innermost group 3[c] expands first; its result becomes part of the outer group.
    The innermost group 3[c] expands first; its result becomes part of the outer group.
    Input:  "2[ab3[c]]x"
    Output: "abcccabcccx"
    Input:  "12[a]"
    Output: "aaaaaaaaaaaa"     # counts can have more than one digit
    Input:  "sys2[tem]"
    Output: "systemtem"        # letters before a group stay in front

    Constraints (assumed)

    • 1 ≤ length of the input ≤ 30; counts are between 1 and 300.
    • The input contains only lowercase letters, digits and square brackets, and is valid.
    • The output fits in memory (its length is at most 10⁵).

    What this question tests

    • Recognising nesting and reaching for a stack (or recursion).
    • Parsing details: multi-digit numbers, letters before and after groups.
    • Building strings efficiently rather than re-copying them on every character.

    Questions to ask first

    1. Can the count have more than one digit? (Here: yes.)
    2. Is the input always valid, with matched brackets and a number before every [? (Here: yes.)
    3. Can a count be 0? (Here: no. If yes, the group simply disappears.)
    4. How large can the output get? Repeats multiply, so a short input can expand to something huge.