Skills101
← All coding problems

Decode String

mediumLinked List & Stack II+20 XPTime limit 2s

A text is compressed with the rule k[text], meaning "text repeated k times". The rules can be nested: 2[a3[b]] is 2[abbb] = abbbabbb. Letters outside brackets stay as they are. Decode the string.

Input: one line, the encoded string: lowercase letters, digits and brackets. It is always well-formed — every number is followed by [, brackets match, and digits only appear as repeat counts.

Output: the decoded string (it is never empty).

Constraints: 1 ≤ encoded length ≤ 10⁴, 1 ≤ k ≤ 300, decoded length ≤ 2·10⁵.

Think about it: use two stacks (or one stack of pairs): on [ save the text built so far and the repeat count, then start a fresh piece; on ] pop, and append the fresh piece repeated k times to the saved text. Careful: a count can have more than one digit.

Sample input 1

3[a]2[bc]

Sample output 1

aaabcbc

Sample input 2

3[a2[c]]

Sample output 2

accaccacc

Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).

Loading editor…

Log in to run and submit your code — it's free.