Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Decode String
• Main tags: String, Stack, Recursion

What the problem is really asking

The input is an encoded string where patterns like 3[ab] mean “repeat ab three times.” The tricky part is that the repeated part can itself contain more encoded pieces, such as 3[a2[c]].

So the real job is not just repeating text. It is keeping track of:

• the repeat count for the current block
• the string built before that block started
• nested blocks that have to finish from the inside out

This is why the problem feels natural with either a stack or recursion.

Why a left-to-right scan works

As the string is read from left to right, only four character types matter:

• digits, which build the current repeat count
• [ which means “start a new nested block”
• ] which means “finish the current block and attach it to its parent”
• letters, which belong to the current block

That means there is no need to repeatedly search for matching substrings or rebuild the whole answer from scratch. Each character can be processed once while carrying just enough state for the current nesting level.

The key insight

When [ appears, the current partial answer is not done. It becomes the prefix for a new inner block.

For example, while parsing 2[abc3[cd]]:

1. 2[ means the next decoded block will be repeated twice.
2. abc becomes the current content of that block.
3. 3[ starts a deeper nested block.
4. cd becomes the content of the deeper block.
5. ] closes the deeper block, so cd becomes cdcdcd.
6. That expanded text is appended back to the outer block, producing abccdcdcd.
7. The final ] closes the outer block, so the whole thing is repeated twice.

The important pattern is:

• push the outer context when entering a bracketed block
• decode the inner block completely
• pop the outer context and stitch the result back in

That is exactly what a stack is for.

How to derive the optimal solution

One clean derivation is:

1. A repeat count only becomes meaningful when [ appears.
2. A substring only becomes complete when ] appears.
3. Nested brackets mean unfinished outer work must be paused.
4. Paused work should be resumed in reverse order of nesting.

Reverse nesting order is a stack.

So the iterative solution keeps:

• current_repeat_count for digits being read now
• current_parts for the decoded text at the current depth
• a stack of saved outer frames, where each frame stores the earlier prefix and the repeat count for the nested block

When ] appears, the current block is joined into a string, repeated, and appended to the previous frame.

Optimal solution choices

There are two standard optimal ways to solve this problem:

• Iterative stack: usually the best interview and production choice because it is explicit and avoids recursion-depth limits.
• Recursive parser: conceptually elegant because each function call naturally handles one bracketed block.

Both approaches do the same amount of real work.

• Time: O(n + m), where n is the encoded length and m is the decoded output length
• Space: O(d + m), where d is nesting depth and m is the decoded output length

The output size matters because the algorithm must actually build the decoded string.

Best way to think about it

Do not think of this as “replace brackets.”

Think of it as:

• accumulate plain characters for the current level
• save the current level when a new nested block begins
• finish the inner block first
• expand it and attach it back to its parent

Once that model is clear, the implementation becomes short and reliable.

Python solution

from dataclasses import dataclass


@dataclass
class DecodeFrame:
    """State that must be restored after a nested block finishes."""

    prefix_parts: list[str]
    repeat_count: int


def decode_string(encoded_text: str) -> str:
    """Decode a LeetCode-style repetition expression such as '3[a2[c]]'."""
    frame_stack: list[DecodeFrame] = []
    current_parts: list[str] = []
    current_repeat_count = 0

    for char in encoded_text:
        if char.isdigit():
            current_repeat_count = _extend_repeat_count(
                current_repeat_count=current_repeat_count,
                digit_char=char,
            )
        elif char == "[":
            # Save the outer context before decoding the nested block.
            frame_stack.append(
                DecodeFrame(
                    prefix_parts=current_parts,
                    repeat_count=current_repeat_count,
                )
            )
            current_parts = []
            current_repeat_count = 0
        elif char == "]":
            current_parts = _close_current_frame(
                frame_stack=frame_stack,
                current_parts=current_parts,
            )
        else:
            current_parts.append(char)

    if frame_stack:
        raise ValueError("Encoded text ended before all brackets were closed.")

    return "".join(current_parts)


def _extend_repeat_count(current_repeat_count: int, digit_char: str) -> int:
    """Append one digit to a possibly multi-digit repeat count."""
    return current_repeat_count * 10 + int(digit_char)


def _close_current_frame(
    frame_stack: list[DecodeFrame],
    current_parts: list[str],
) -> list[str]:
    """Expand the current block and attach it back to its parent frame."""
    if not frame_stack:
        raise ValueError("Encountered a closing bracket without an opening bracket.")

    completed_segment = "".join(current_parts)
    frame = frame_stack.pop()
    expanded_segment = completed_segment * frame.repeat_count

    frame.prefix_parts.append(expanded_segment)
    return frame.prefix_parts


class Solution:
    def decodeString(self, s: str) -> str:
        return decode_string(s)