394. Decode String

At a Glance

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

Problem (one-liner)

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

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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 [)

Similar Problems

• 20. Valid Parentheses — bracket matching without repeats
• 22. Generate Parentheses — structured bracket recursion
• 739. Daily Temperatures — stack for deferred resolution (different domain)

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