Decode String

Problem

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

Examples

The brute-force approach

Recursively parse the string. When you see a number followed by '[', find the matching ']', decode the substring, repeat it, and continue.

# Recursive parser — harder to implement for nested brackets.
# Stack-based iteration is cleaner.

Recursion works but tracking matching brackets is error-prone. The stack approach is O(n × max_k) and handles nesting naturally.

Spotting the pattern

This is a Stack problem. The key question to ask yourself:

What does each stack frame represent, and why do you reset current_string to empty when pushing onto the stack?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.