Decode String (LC 394)

Problem Statement

Given an encoded string, return its decoded form. The encoding rule is k[encoded_string], meaning the bracketed substring is repeated exactly k times. k is a positive integer. Nesting is allowed.

Example 1:

Input:  s = "3[a]2[bc]"
Output: "aaabcbc"

Example 2:

Input:  s = "3[a2[c]]"
Output: "accaccacc"

Example 3:

Input:  s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"

Constraints:

• 1 <= s.length <= 30
• s consists of lowercase letters, digits, [, ].
• 1 <= k <= 300.
• Result length fits in int range.

Difficulty: Medium

---

Pattern Recognition

• Input structure: string with balanced brackets and repetition counts.
• What are we producing? a decoded string.
• Pattern: stack (nested structure means LIFO). Alternatively, recursive descent parser.
• Why: brackets nest, and you only know how to finalize a k[...] chunk when you hit its closing ]. The stack remembers the multiplier and the "string built so far" at the outer level.

---

Approach

Brute Force

Repeatedly scan for the innermost k[...] and expand via string replacement. Each scan is O(n); replacements can blow up. Works but clunky.

Optimal — Two Stacks

Key Insight: Keep two stacks: one for multipliers (ks) and one for "the string we were building before this [". Whenever ] closes, pop a multiplier and a prefix, and compose.

numStack = []
strStack = []
cur = ""
k = 0
for ch in s:
    if ch is digit:
        k = k * 10 + int(ch)
    elif ch == '[':
        numStack.push(k)
        strStack.push(cur)
        k = 0
        cur = ""
    elif ch == ']':
        prevStr = strStack.pop()
        times = numStack.pop()
        cur = prevStr + cur.repeat(times)
    else:
        cur += ch
return cur

Time: O(output length) — must produce each character. Space: O(output length) for the final string plus O(depth) for the stacks.

Alternative — Recursive Parser

Define decode(i) that reads from index i, returning (decoded, nextIndex). When you see a digit, read the full number, skip [, recurse, expect ], multiply, append. Clean and readable.

---

Walkthrough

s = "3[a2[c]]".

i	ch	k	cur	numStack	strStack	notes
0	3	3	""	[]	[]	read digit
1	[	0	""	[3]	[""]	push k, reset cur
2	a	0	"a"	[3]	[""]	append letter
3	2	2	"a"	[3]	[""]	digit
4	[	0	""	[3, 2]	["", "a"]	push
5	c	0	"c"	[3, 2]	["", "a"]
6	]	0	"a" + "c"*2 = "acc"	[3]	[""]	pop, compose
7	]	0	"" + "acc"*3 = "accaccacc"	[]	[]	pop, compose

Result: "accaccacc".

---

Implementation

TypeScript

function decodeString(s: string): string {
    const numStack: number[] = [];
    const strStack: string[] = [];
    let cur = "";
    let k = 0;

    for (const ch of s) {
        if (ch >= '0' && ch <= '9') {
            k = k * 10 + (ch.charCodeAt(0) - 48);
        } else if (ch === '[') {
            numStack.push(k);
            strStack.push(cur);
            k = 0;
            cur = "";
        } else if (ch === ']') {
            const prev = strStack.pop()!;
            const times = numStack.pop()!;
            cur = prev + cur.repeat(times);
        } else {
            cur += ch;
        }
    }
    return cur;
}

C++

string decodeString(string s) {
    vector<int> numStack;
    vector<string> strStack;
    string cur;
    int k = 0;
    for (char ch : s) {
        if (isdigit(ch)) {
            k = k * 10 + (ch - '0');
        } else if (ch == '[') {
            numStack.push_back(k);
            strStack.push_back(cur);
            k = 0;
            cur.clear();
        } else if (ch == ']') {
            int times = numStack.back(); numStack.pop_back();
            string prev = strStack.back(); strStack.pop_back();
            string expanded;
            expanded.reserve(prev.size() + cur.size() * times);
            expanded = prev;
            for (int i = 0; i < times; i++) expanded += cur;
            cur = expanded;
        } else {
            cur += ch;
        }
    }
    return cur;
}

Watch out:

1. Multi-digit counts: "12[a]" — do not reset k when reading each digit. Accumulate via k = k * 10 + d.
2. Reset k = 0 and cur = "" exactly when you see [, not ] — getting the reset timing wrong corrupts nested scopes.
3. The result can be long (3 * 300 * ... nested); use efficient string building (cur.repeat in TS, reserve + append in C++).

---

Complexity Analysis

	Time	Space
Brute Replacement	O(n * output)	O(output)
Two Stacks	O(output)	O(output)
Recursive Parser	O(output)	O(output) stack depth

Bottleneck: producing the output characters is unavoidable.

---

Edge Cases

1. No brackets — e.g., "abc". Return unchanged; the bracket branches never fire.
2. Multi-digit multiplier — "100[a]". Accumulator handles it.
3. Nested same depth — "3[a]2[bc]". Each is handled independently.
4. Deep nesting — stack depth up to n/3 (each k[ takes at least 2 chars). Fine at n=30.
5. Letters after a closing bracket — "3[a]b". After popping, append 'b' to the already-composed cur.
6. Empty brackets — "3[]". cur is "", repeat yields "".

---

Related Problems

• LC 224 — Basic Calculator — Nested parenthesis evaluation; use a sign+stack pattern.
• LC 726 — Number of Atoms — Chemical formula parsing; essentially decode-string with counts.
• LC 736 — Parse Lisp Expression — Recursive parser on nested scopes with variables.
• LC 1096 — Brace Expansion II — Nested grammar with union/concatenation.

---

What Is Expected at Each Level

Junior: Recognizes stack-based approach with guidance. Implements with small bugs around multi-digit or reset timing.

Mid-level: Clean two-stack implementation, handles multi-digit counts and edge cases without prompting, states O(output) complexity.

Senior (L4 target): Writes either two-stack or recursive-descent fluently, discusses parser theory (context-free grammar), and pivots naturally to LC 726 or LC 1096 when the interviewer adds grammar rules. Discusses string-building cost in the target language (TS template concatenation vs C++ reserve) — Google interviewers do grade that level of production care.