Decode String

You are given an encoded string s, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. There will not be input like 3a, 2[4], a[a] or a[2].

The test cases are generated so that the length of the output will never exceed 100,000.

Example 1:

Input: s = "2[a3[b]]c"

Output: "abbbabbbc"

Example 2:

Input: s = "axb3[z]4[c]"

Output: "axbzzzcccc"

Example 3:

Input: s = "ab2[c]3[d]1[x]"

Output: "abccdddx"

Constraints:

• 1 <= s.length <= 30
• s is made up of lowercase English letters, digits, and square brackets '[]'.
• All the integers in s are in the range [1, 300].
• s is guaranteed to be a valid input.

Company Tags

Please upgrade to NeetCode Pro to view company tags.