MediumStacks

Decode String

Explanation & Solution

Description

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.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

The test cases are generated so that the length of the output will never exceed 10^5.

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

Output: "aaabcbc"

Constraints

1 <= s.length <= 30
s consists of lowercase English letters, digits, and square brackets '[]'
s is guaranteed to be a valid input
All the integers in s are in the range [1, 300]

Approach

Stacks pattern

1. Two Stacks

Count stack: stores the repeat counts (k values)
String stack: stores the string built before each [

2. Process Each Character

Digit: Build the number k (handles multi-digit numbers)
`[`: Push the current k and currentStr onto their stacks, then reset both
`]`: Pop the count and previous string, repeat currentStr that many times, and prepend the previous string
Letter: Append to currentStr

3. Nested Decoding

The stacks naturally handle nested encodings like 3[a2[c]]
Inner brackets are decoded first, and their results are used by outer brackets

Key Insight

The stack saves the context (accumulated string + repeat count) before entering a nested bracket
Upon closing ], we restore context and apply the repetition
This is essentially simulating the recursion stack iteratively
Time: O(output length), Space: O(nesting depth)

Visualization

Input:

[3, [, a, ], 2, [, b, c, ]]

—

Press ▶ or use ← → to step through

Left (L)Right (R)ConvergedDone

5 steps

Solution Code

Largest Rectangle in Histogram

Asteroid Collision