Decode String

MediumRecursion · Stack🧩 Recursion & Divide and Conquer LeetCode #394 ↗Updated Oct 30, 2026

Problem

A string is compressed with the rule k[body], meaning body written out k times; groups may be nested and mixed with plain letters. Given a valid encoded string s, return the fully expanded string.

Input3[a]2[bc]Outputaaabcbc

Input3[a2[c]]Outputaccaccacc

Input2[abc]3[cd]efOutputabcabccdcdcdef

1 ≤ |s| ≤ 30 · lowercase letters, digits, [ ] · 1 ≤ k ≤ 300 · output length ≤ 10⁵ · input always valid

Try it yourself

Java

class Solution {
    public String decodeString(String s) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Every [ opens a new “context” that must be finished before the outer one can continue. Save the outer text and its k on [, and on ] glue k copies of the inner text back onto it — recursion or a stack. (Below: L = output length, d = nesting depth.)

PatternRecursion & Divide and Conquer

Instinct If the answer for n items can be built from the same problem on halves (or smaller pieces) plus a cheap combine step - split, recurse, merge.

Memory hack Split it, trust it, stitch it - nail the base case, take the leap of faith on smaller calls, then glue their answers together.

Open the Recursion & Divide and Conquer guide →

Approaches

Brute ForceExpand Innermost Group Repeatedly

Time O(p·(n+L))Space O(n+L)

The first ] and the last [ before it form an innermost group whose body is letters only. Replace k[body] with body × k and repeat until no brackets remain. Each of the p expansions rebuilds the whole string.

Java

public String decodeString(String s) {
    int close;
    while ((close = s.indexOf(']')) != -1) {
        int open = s.lastIndexOf('[', close); // innermost pair
        int start = open;
        while (start > 0 && Character.isDigit(s.charAt(start - 1))) start--;
        int k = Integer.parseInt(s.substring(start, open));
        String body = s.substring(open + 1, close).repeat(k);
        s = s.substring(0, start) + body + s.substring(close + 1);
    }
    return s;
}

Simple string surgery, but re-copies the entire string once per bracket pair.

BetterRecursive Descent

Time O(n + d·L)Space O(n+L)

decode() reads letters until it hits ] or the end. On a number it parses k, skips [, recursively decodes the inner part, skips ] and appends it k times. A shared index means every input character is read once.

Java

private int i;
public String decodeString(String s) {
    i = 0;
    return decode(s);
}
private String decode(String s) {
    StringBuilder sb = new StringBuilder();
    while (i < s.length() && s.charAt(i) != ']') {
        char c = s.charAt(i);
        if (Character.isDigit(c)) {
            int k = 0;
            while (Character.isDigit(s.charAt(i))) k = k * 10 + (s.charAt(i++) - '0');
            i++;                     // skip '['
            String inner = decode(s);
            i++;                     // skip ']'
            sb.append(inner.repeat(k));
        } else {
            sb.append(c);
            i++;
        }
    }
    return sb.toString();
}

Clean single scan; recursion depth equals nesting depth.

OptimalTwo Stacks (Iterative)

Time O(n + d·L)Space O(n+L)

Simulate the recursion explicitly. On [ push the pending count and the text built so far, then start fresh. On ] pop both and append k copies of the current text to the popped builder. Pushing the builder (not a String copy) keeps appends amortised O(1).

Java

public String decodeString(String s) {
    Deque<Integer> counts = new ArrayDeque<>();
    Deque<StringBuilder> texts = new ArrayDeque<>();
    StringBuilder cur = new StringBuilder();
    int k = 0;
    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            counts.push(k);
            texts.push(cur);
            cur = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            StringBuilder prev = texts.pop();
            prev.append(cur.toString().repeat(counts.pop()));
            cur = prev;
        } else {
            cur.append(c);
        }
    }
    return cur.toString();
}

Dry run3[a2[c]]

i current char changed

i=1
3

[
i
a

2

[

c

]

]

push(3, ""), cur=""
i=2
3

[

a
i
2

[

c

]

]

cur="a"
i=4
3

[

a

2

[
i
c

]

]

push(2, "a"), cur=""
i=5
3

[

a

2

[

c
i
]

]

cur="c"
i=6
3

[

a

2

[

c

]
i
]

cur="a"+2×"c"="acc"
i=7
3

[

a

2

[

c

]

]
i
""+3×"acc" ✔

Same cost as recursion, no call-stack risk — the usual interview answer.

Pro tip

Multi-digit counts (12[a]) are the classic trap — always accumulate k = k*10 + digit and reset it after pushing.

At a glance

Level	Approach	Time	Space
Brute Force	Expand Innermost Group Repeatedly	`O(p·(n+L))`	`O(n+L)`
Better	Recursive Descent	`O(n + d·L)`	`O(n+L)`
Optimal	Two Stacks (Iterative)	`O(n + d·L)`	`O(n+L)`

Common pitfalls

Reading only one digit of k — breaks on 10[a] or 300[x].
Forgetting to reset k / cur after [.
Pushing cur.toString() and rebuilding the prefix on every ] — quadratic copying.

Interview tips

Say it is a grammar: str := (letter | k[str])* — recursion falls out of it.
Mention complexity depends on output length, not just |s|.
Trace 3[a2[c]] aloud, showing what each stack holds.

Pattern

Nested brackets → recursion / stack of contexts → parse, evaluate or expand nested structures.

My notes saved in this browser