Decode string

An encoded string uses k[text] to mean text repeated k times, and brackets can nest. Given an encoded string, return the decoded string.

Before you code

Nested brackets are nested work: when you meet [, you start a new piece and must remember the piece you were in the middle of, and its repeat count. That is exactly what a call stack does for a recursive function, and what an explicit stack can do for a loop.

Hints

1. Recursive version: a function decodes until it reaches ] or the end, and calls itself after each k[.
2. Iterative version: on [, push (current_text, k) and start a fresh current_text. On ], pop (previous, k) and set current_text = previous + current_text * k.
3. Numbers can have several digits, as in 10[a]. Build k digit by digit.
4. Compare the two versions on a string nested 10,000 levels deep.

Production & complexity notes

When solving Decode string on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in The call stack is a stack to reinforce the underlying pattern.

What it practices

Replacing recursion with an explicit stack, from The call stack is a stack.