All problems

Decode String

Medium · stack

You are given an encoded string s. It is made of lowercase letters, digits, and the brackets [ and ].

The encoding rule is k[text]: the text inside the brackets is repeated exactly k times, where k is a positive whole number (it can have several digits, such as 12). The text can itself contain letters and further encoded parts, so repeats can be nested. Letters outside any brackets are copied as they are.

Return the decoded string. For example, "2[ab]c" decodes to "ababc" and "2[a2[b]]" decodes to "abbabb".

The input is always valid: the brackets are balanced, every [ is directly preceded by its repeat number, and digits appear only as repeat numbers (so the original text never contains digits). The decoded string is never longer than 100,000 characters.

Examples

Example 1

Input: s = "2[ab]3[c]"

Output: "ababccc"

ab is repeated twice and c three times.

Example 2

Input: s = "x2[y3[z]]w"

Output: "xyzzzyzzzw"

The inner 3[z] gives zzz. The outer part repeats y followed by zzz twice, and x and w are copied around it.

Example 3

Input: s = "hello"

Output: "hello"

There are no brackets, so nothing is repeated.

Constraints

• 1 <= len(s) <= 10^4
• s contains only lowercase letters, digits, [ and ]
• The brackets are balanced and every [ is preceded by its repeat number k, with 1 <= k <= 10^5
• Brackets are nested at most 300 levels deep
• The decoded string has at most 10^5 characters