DSA Decoding a Repeated String

The problem

Decoding a repeated string expands a pattern into full text. A number before an opening bracket repeats the text inside that bracket pair. Bracket pairs may nest, and inner pairs expand before the outer text around them is repeated.

Letters outside any bracket stay as they are. A repeat count may hold several digits. The cases below are the ones this article uses throughout.

cases = [
    ("3[a2[c]]", "accaccacc"),
    ("3[a]2[bc]", "aaabcbc"),
    ("2[abc]3[cd]ef", "abcabccdcdcdef"),
    ("10[x]", "xxxxxxxxxx"),
    ("abc", "abc"),
    ("", ""),
]
for text, expected in cases:
    print("pattern", repr(text), "-> decoded:", repr(expected))

Read one row at a time. In the first row, the inner 2[c] becomes cc inside each of the three repeats. The fourth row shows a two-digit count.

Intuition: one saved frame is not enough

The first idea saves the state once when a bracket opens. It saves the text built so far and the repeat count. At the closing bracket it repeats the inner text and joins the saved text back on.

One saved frame handles one level of nesting. A second opening bracket overwrites the saved frame, and the outer state is lost. The run below shows the loss on a two-level pattern.

def flat_decode(text):
    saved = ("", 0)
    current = ""
    number = 0
    for ch in text:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch == "[":
            saved = (current, number)
            current = ""
            number = 0
        elif ch == "]":
            outer, count = saved
            current = outer + count * current
        else:
            current += ch
    return current

print("one-level pattern:", flat_decode("3[ab]"))
print("nested pattern:", flat_decode("2[a3[b]]"))
print("correct nested answer: abbbabbb")

The nested answer is wrong in both length and shape. The outer count of 2 was overwritten by the inner count of 3. Saving state once is not enough, because nesting can go several levels deep.

Brute force: expand the innermost pair, again and again

The brute force rewrites the string itself. Each step finds the innermost bracket pair, the last opening bracket before the first closing one. It replaces that pair and its count with the repeated text, then starts over on the new string.

A counter records the characters scanned across all the rewrites. Each rewrite rescans the string from the start, so the scanning grows with both the pattern length and the number of pairs.

def decode_brute(text):
    scanned = 0
    while "[" in text:
        scanned += len(text)
        close = text.index("]")
        open_ = text.rindex("[", 0, close)
        start = open_
        while start - 1 >= 0 and text[start - 1].isdigit():
            start -= 1
        count = int(text[start:open_])
        inner = text[open_ + 1:close]
        text = text[:start] + count * inner + text[close + 1:]
    return text, scanned

result, scanned = decode_brute("3[a2[c]]")
print("decoded:", result)
print("characters scanned:", scanned)
result, scanned = decode_brute("3[a]2[bc]")
print("second case:", result)
print("characters scanned:", scanned)

The method is correct, because the innermost pair never contains a bracket of its own. Its weakness is the repeated scanning and rebuilding. The stack below reads the pattern once and never rebuilds it.

The optimal solution: a stack of frames, closed from the inside out

A stack of frames holds the outer text and the repeat count at each opening bracket, and each closing bracket pops one frame, repeats the inner text, and joins it to that outer text. That one sentence is the whole method.

A frame is one stack entry holding a count and a piece of text. Digits accumulate into a running number before a bracket opens, so multi-digit counts work with no special case. Letters simply extend the current text.

Nested brackets close from the inside out. That is exactly stack order, with the most recent frame on top. The current text after the last closing bracket is the full answer.

def decode(text):
    stack = []
    current = ""
    number = 0
    for ch in text:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch == "[":
            stack.append((current, number))
            current = ""
            number = 0
        elif ch == "]":
            outer, count = stack.pop()
            current = outer + count * current
        else:
            current += ch
    return current

cases = [
    ("3[a2[c]]", "accaccacc"),
    ("3[a]2[bc]", "aaabcbc"),
    ("2[abc]3[cd]ef", "abcabccdcdcdef"),
    ("10[x]", "xxxxxxxxxx"),
    ("abc", "abc"),
    ("", ""),
]
for text, expected in cases:
    result = decode(text)
    print("pattern", repr(text), "->", repr(result), "expected:", repr(expected), "match:", result == expected)

All six cases pass. The two-digit count in the fourth row is built by the same digit step as any single digit. The empty pattern decodes to the empty string with no frames at all.

Walkthrough: decoding 3[a2[c]] character by character

The walk reads the first case one character at a time. The stack of frames and the current text print after each character. Digits change only the running count, so their lines show the state they leave behind.

text = "3[a2[c]]"
stack = []
current = ""
number = 0
for ch in text:
    if ch.isdigit():
        number = number * 10 + int(ch)
    elif ch == "[":
        stack.append((current, number))
        current = ""
        number = 0
    elif ch == "]":
        outer, count = stack.pop()
        current = outer + count * current
    else:
        current += ch
    print("char", repr(ch), "- stack:", stack, "current:", repr(current))
print("decoded:", current)

The inner bracket closes first and turns c into cc joined after a. The outer bracket then repeats acc three times. The answer is read straight off the final current text.

Complexity

The stack method reads each character of the pattern once, so its pattern-scanning time is O(n) for a pattern of n characters, plus the cost of writing the output itself. The rewriting method rescans the whole string once per bracket pair, so its scanning grows with the pair count times the string length.

The stack holds at most one frame per level of nesting, so its space is O(d) for a nesting depth of d. The rewriting method holds only the string being rebuilt, so its extra space is O(1) beyond that string.

def decode_brute_scans(text):
    scanned = 0
    while "[" in text:
        scanned += len(text)
        close = text.index("]")
        open_ = text.rindex("[", 0, close)
        start = open_
        while start - 1 >= 0 and text[start - 1].isdigit():
            start -= 1
        count = int(text[start:open_])
        inner = text[open_ + 1:close]
        text = text[:start] + count * inner + text[close + 1:]
    return scanned

for depth in (2, 3, 4):
    text = "2[" * depth + "a" + "]" * depth
    print("depth", depth, "- brute scans:", decode_brute_scans(text), " stack reads:", len(text))

Each extra level of nesting adds a full rescan to the rewriting method. The stack method reads the longer pattern once, so its count grows only with the pattern itself.

Edge cases and pitfalls

Reading the count as a single digit is the classic mistake. The pattern 10[x] holds ten x values, not one x followed by a stray 0. Digits must accumulate until the bracket opens, exactly as the running number does.

Joining in the wrong order is the second mistake. The repeated inner text goes after the outer text stored in the frame. Reversing the join scrambles every pattern that has letters before a bracket.

def decode(text):
    stack = []
    current = ""
    number = 0
    for ch in text:
        if ch.isdigit():
            number = number * 10 + int(ch)
        elif ch == "[":
            stack.append((current, number))
            current = ""
            number = 0
        elif ch == "]":
            outer, count = stack.pop()
            current = outer + count * current
        else:
            current += ch
    return current

print("empty pattern:", repr(decode("")))
print("no brackets:", repr(decode("abc")))
print("two-digit count:", repr(decode("12[a]")))
print("count of one:", repr(decode("1[ab]")))
print("deep nesting:", repr(decode("2[2[2[a]]]")))
print("letters after a bracket:", repr(decode("3[a]b")))

The deep nesting row doubles three times and gives eight copies of a. The count of one still pushes and pops a frame, so it follows the same path as every other bracket.