Workspace

Problem workspace

3 day streakD

Decode a Repeated String

MediumStacksExpressions & parsing

The challenge

Decode nested k[encoded] groups, preserving literal letters.

ASCII letters, positive integer repeat counts, balanced brackets. Decoded length L ≤ 100,000.

Example

3[a2[c]] → accaccacc.

Use the walkthrough below to inspect the input and each state change.

See Decode a Repeated String, step by step

Inspect each push, pop, and recorded answer. Entries such as 2: 5 mean index: value.

Zero-based input · top labeled explicitlyLIFO
Input and stack stateCurrent input index: -1. Main stack bottom to top: []. Auxiliary stack · bottom → top: []. Read the input in order. The stack keeps only the state needed to resolve the next item.30[1a223[4c5]6]7Main stack · bottom → top ↑emptyAuxiliary · bottom → top ↑empty
Current input index
—
Main stack size
0
Step 01 / 10

Start with an empty stack

Read the input in order. The stack keeps only the state needed to resolve the next item.

Answer so far

Not recorded yet
Main stack · bottom → top
Empty
Auxiliary stack · bottom → top
Empty
View exact input and state

Input: ["3","[","a","2","[","c","]","]"]

Main stack: []. Auxiliary stack · bottom → top: [].

Put it into code

Save (prefix, count) on [, then restore and expand on ].

Indices are zero-based. C++ uses C++17 or later.

def solve(values):
    stack = []
    text, count = '', 0
    for c in values:
        if c.isdigit(): count = 10 * count + int(c)
        elif c == '[':
            stack.append((text, count))
            text, count = '', 0
        elif c == ']':
            prefix, repeat = stack.pop()
            text = prefix + text * repeat
        else: text += c
    return text

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap