Expand Repeat Brackets

Medium

A string was compressed like this: a fragment repeated k times in a row is written as k[fragment]. A fragment may itself contain such groups, nested to any depth. Given the compressed string code, return the original string. The notation is always well-formed: brackets are balanced, every [ is preceded by a repeat count, and there are no other digits in the string (the letters themselves never include digits).

Example 1

code="2[x3[y]]z" → 'xyyyxyyyz'

The inner group 3[y] gives yyy, the whole 2[...] repeats xyyy twice, and z is appended at the end.

Example 2

code="ab4[c]" → 'abcccc'

Letters outside brackets stay as they are, and c is repeated 4 times.

Example 3

code="3[2[o]k]" → 'ookookook'

Constraints

1 ≤ len(code) ≤ 30
code consists of lowercase English letters, digits and the brackets [ ]
Every repeat count is between 1 and 300
The result is at most 10⁵ characters long

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Stack Recursion String

Similar problems

Evaluating Nested Conditions Medium Plus-Minus Calculator With Brackets Hard A Calculator With Brackets and Variables Hard Simplify a Letter Polynomial Hard Calculator With Brackets and Four Operations Hard

Input

code="2[x3[y]]z"

Expected

'xyyyxyyyz'

Run checks the first 3 tests in your browser. Submit checks all 128 tests on the server, hidden ones included.