DSA Factory
Free Recursion lessonsRecursion · Stage 4 · Mastery · Step 1

Unfold the brackets

Expand a string where a number before a bracketed part means repeat it, and parts can sit inside parts. About 18 minutes.

A bracket is a smaller problem

The text 3[a2[c]] means: take the group inside the outer brackets and repeat it three times. That group is the letter a followed by two copies of c, which is "acc". So the whole text decodes to "accaccacc".

The inside of a bracket is exactly the same kind of text, so decode it by calling the same function. Walk along the text. A letter is added as it is. A number is remembered. An opening bracket starts a recursive call that returns when it meets the matching closing bracket.

Letter: add it to the output.
Number then [: decode the inside, repeat it that many times.
]: ends this call.
In code
depth = best = 0
for ch in s:
    if ch == "[":
        depth += 1
        best = max(best, depth)
    elif ch == "]":
        depth -= 1
Decoding the example one character at a time.
2
0
[
1
b
2
3
3
[
4
d
5
]
6
]
7
leftright

A 2: remember the count 2.

Move 1 of 7

Return the position too

A recursive call decodes the inside of a bracket, but the outer call needs to know where to carry on afterwards: just past the matching closing bracket. So the call returns two things, the decoded text and the position where it stopped.

Numbers can have several digits, such as 12, so build them up digit by digit. Reset the count after using it.

Return two values: the decoded text and the stopping position.
Multi-digit numbers: multiply the old count by 10 and add the digit.
Quick check

What does 2[ab3[c]] decode to?

  1. Aabcccabccc
  2. Babcabc
  3. Cababccc
Show the answer

abcccabccc. Inside, 3[c] is ccc, so the group is abccc, repeated twice.

Your problem

Unfold the brackets

s is an encoded string made of lowercase letters, digits and square brackets. A number k followed by a bracketed part means that part is repeated k times, and bracketed parts can be nested. The brackets are always balanced, and every number is directly followed by an opening bracket. Return the decoded string.

Example
s = "3[a2[c]]" → "accaccacc"

1 ≤ length ≤ 60 · numbers are between 1 and 20 · the decoded length is at most 3,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve