067. Decode Nested Repetition

Bridge · Download this solution · All solutions and shared helpers

Problem

Decode a valid expression made from lowercase letters and groups count[expression], where count is a positive decimal integer and groups may nest. Concatenation is implicit. Empty input decodes to an empty string. Return the fully expanded text.

Examples

Example 1

decode_repetition("3[a2[c]]")
=> 'accaccacc'

The inner group is completed before the outer repetition.

Example 2

decode_repetition("10[a]")
=> 'aaaaaaaaaa'

Counts may contain multiple digits.

Example 3

decode_repetition("")
=> ''

The outer context has no fragments.

Reveal the worked solution and reasoning

Why this mechanism works

Opening a group suspends a parent output context and its repetition count. Closing it completes the child text, repeats that text, and appends it to the restored parent. A stack preserves these contexts in nesting order. Multi-digit counts are accumulated numerically before '['.

State and boundaries

pieces holds completed fragments in the active context. stack holds suspended (parent_fragments, repeat_count) pairs. count is the numeric prefix being read.

Protocol

Accumulate digits into count.
On '[' save parent and count, then start a fresh child.
Append letters as fragments.
On ']' join and repeat the child, restore its parent and append the result.
Join the outer fragments.

Visualization

3[a2[c]]
inner 2[c] -> cc
parent a + cc -> acc
outer 3[acc] -> accaccacc

Python implementation

def decode_repetition(text):
    stack = []
    pieces = []
    count = 0
    for char in text:
        if char.isdigit():
            count = count * 10 + int(char)
        elif char == '[':
            stack.append((pieces, count))
            pieces, count = [], 0
        elif char == ']':
            parent, repeat = stack.pop()
            parent.append(''.join(pieces) * repeat)
            pieces = parent
        else:
            pieces.append(char)
    return ''.join(pieces)

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

decode_repetition("3[a2[c]]")

L2 decode_repetition: stack = []
text='3[a2[c]]'; stack=[]

L3 decode_repetition: pieces = []
text='3[a2[c]]'; stack=[]; pieces=[]

L4 decode_repetition: count = 0
text='3[a2[c]]'; stack=[]; pieces=[]; count=0

L5 decode_repetition: for char in text:
text='3[a2[c]]'; stack=[]; pieces=[]; count=0; char='3'

L7 decode_repetition: count = count * 10 + int(char)
text='3[a2[c]]'; stack=[]; pieces=[]; count=3; char='3'

L5 decode_repetition: for char in text:
text='3[a2[c]]'; stack=[]; pieces=[]; count=3; char='['

L9 decode_repetition: stack.append((pieces, count))
text='3[a2[c]]'; stack=[([], 3)]; pieces=[]; count=3; char='['

L10 decode_repetition: pieces, count = [], 0
text='3[a2[c]]'; stack=[([], 3)]; pieces=[]; count=0; char='['

... 12 intermediate state changes omitted ...

L14 decode_repetition: pieces = parent
text='3[a2[c]]'; stack=[([], 3)]; pieces=['a', 'cc']; count=0; char=']'; parent=['a', 'cc']; repeat=2

L12 decode_repetition: parent, repeat = stack.pop()
text='3[a2[c]]'; stack=[]; pieces=['a', 'cc']; count=0; char=']'; parent=[]; repeat=3

L13 decode_repetition: parent.append(''.join(pieces) * repeat)
text='3[a2[c]]'; stack=[]; pieces=['a', 'cc']; count=0; char=']'; parent=['accaccacc']; repeat=3

L14 decode_repetition: pieces = parent
text='3[a2[c]]'; stack=[]; pieces=['accaccacc']; count=0; char=']'; parent=['accaccacc']; repeat=3

Result: 'accaccacc'. The inner group is completed before the outer repetition.

decode_repetition("10[a]")

L2 decode_repetition: stack = []
text='10[a]'; stack=[]

L3 decode_repetition: pieces = []
text='10[a]'; stack=[]; pieces=[]

L4 decode_repetition: count = 0
text='10[a]'; stack=[]; pieces=[]; count=0

L5 decode_repetition: for char in text:
text='10[a]'; stack=[]; pieces=[]; count=0; char='1'

L7 decode_repetition: count = count * 10 + int(char)
text='10[a]'; stack=[]; pieces=[]; count=1; char='1'

L5 decode_repetition: for char in text:
text='10[a]'; stack=[]; pieces=[]; count=1; char='0'

L7 decode_repetition: count = count * 10 + int(char)
text='10[a]'; stack=[]; pieces=[]; count=10; char='0'

L5 decode_repetition: for char in text:
text='10[a]'; stack=[]; pieces=[]; count=10; char='['

... 4 intermediate state changes omitted ...

L5 decode_repetition: for char in text:
text='10[a]'; stack=[([], 10)]; pieces=['a']; count=0; char=']'

L12 decode_repetition: parent, repeat = stack.pop()
text='10[a]'; stack=[]; pieces=['a']; count=0; char=']'; parent=[]; repeat=10

L13 decode_repetition: parent.append(''.join(pieces) * repeat)
text='10[a]'; stack=[]; pieces=['a']; count=0; char=']'; parent=['aaaaaaaaaa']; repeat=10

L14 decode_repetition: pieces = parent
text='10[a]'; stack=[]; pieces=['aaaaaaaaaa']; count=0; char=']'; parent=['aaaaaaaaaa']; repeat=10

Result: 'aaaaaaaaaa'. Counts may contain multiple digits.

Why the solution is correct

A context's fragments decode its completed components in order. Closing a valid group has all child components available, so joining and repeating gives that group's exact meaning. Restoring the enclosing context preserves concatenation order; the final join decodes the outer expression.

Time and space

O(n+L*d) conservative time for nesting depth d and final output length L, because nested expansions may recopy text; O(n+L+d) space. Output can be exponentially larger than encoded input.

Common mistakes

Resetting count too late reuses digits across groups. One shared current string without saved parent context loses text before a nested group.

Reasoning card

State: pieces holds completed fragments in the active context. stack holds suspended (parent_fragments, repeat_count) pairs. count is the numeric prefix being read.

Invariant: Current buffers describe the active nesting context.

Decision to rehearse: Save outer string/count when entering brackets; combine when closing.

Finish: Join the outer fragments

Transfer exercise

Compute only the decoded length, avoiding materializing a potentially enormous string.