394. Decode String

Quick Identifier

Topic: stack
Pattern: Stack (nested expansion)
Difficulty: Medium
Companies: Google, Amazon, Meta, Bloomberg, Apple
Frequency: High
LeetCode: 394

Quick Sights

Time Complexity: See optimal approach. from the optimal approach.
Space Complexity: See optimal approach. from the optimal approach.
Core Mechanism: Decode an encoded string where k[encoded] repeats encoded exactly k times; brackets nest. Return fully expanded string (length can explode).

Concept Explanation

Decode an encoded string where k[encoded] repeats encoded exactly k times; brackets nest. Return fully expanded string (length can explode).

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

Nested brackets with numeric repeat counts
DFS or explicit stacks for (partialString, repeatCount) frames
Numbers may be multi-digit

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Recursive descent — O(max output) time / recursion depth O(n).
Two stacks — current string stack + count stack — linear scan O(n) input, output proportional to expansion.

Optimal Solution

Go

import "strings"

func decodeString(encoded string) string {
	repeatStack := make([]int, 0)
	fragmentStack := []string{""}
	pending := 0
	for _, ch := range encoded {
		switch {
		case ch >= '0' && ch <= '9':
			pending = pending*10 + int(ch-'0')
		case ch == '[':
			repeatStack = append(repeatStack, pending)
			fragmentStack = append(fragmentStack, "")
			pending = 0
		case ch == ']':
			repeat := repeatStack[len(repeatStack)-1]
			repeatStack = repeatStack[:len(repeatStack)-1]
			inner := fragmentStack[len(fragmentStack)-1]
			fragmentStack = fragmentStack[:len(fragmentStack)-1]
			fragmentStack[len(fragmentStack)-1] = fragmentStack[len(fragmentStack)-1] + strings.Repeat(inner, repeat)
		default:
			fragmentStack[len(fragmentStack)-1] = fragmentStack[len(fragmentStack)-1] + string(ch)
		}
	}
	return fragmentStack[0]
}

JavaScript

function decodeString(encoded) {
	const repeatStack = [];
	const fragmentStack = [''];
	let pending = 0;
	for (const char of encoded) {
		if (char >= '0' && char <= '9') {
			pending = pending * 10 + Number(char);
		} else if (char === '[') {
			repeatStack.push(pending);
			fragmentStack.push('');
			pending = 0;
		} else if (char === ']') {
			const repeat = repeatStack.pop();
			const inner = fragmentStack.pop();
			fragmentStack[fragmentStack.length - 1] += inner.repeat(repeat);
		} else {
			fragmentStack[fragmentStack.length - 1] += char;
		}
	}
	return fragmentStack[0];
}

Walkthrough

"3[a2[c]]" → inner 2[c] becomes cc, outer 3[acc] becomes accaccacc.

Invariant: top of fragmentStack is the fragment for the current [ … ] level; on ], repeat the inner fragment and append to the parent.

Edge Cases

10[a] — multi-digit repeat count
Deep nesting — stack depth bounded by bracket depth
Output size can be exponential in input length

Pitfalls

Parsing multi-digit numbers without resetting pending after [
Using repeat = 0 when k was not parsed before [ (always push count on [)

Variants

Decode with length cap — stop if expanded length exceeds limit (streaming interview twist).
Encode the inverse mapping (run-length style) for round-trip design questions.

Mind-Map Tags

#stack #nested-brackets #decode #repeat-string #multi-digit-parse