Decode String

Given an encoded string s, return its fully decoded form. The encoding rule is k[encoded_string], meaning the bracketed substring is repeated exactly k times. The encoding is always valid, repeat counts are positive integers, digits only appear as repeat counts, and bracketed groups may nest.

For example, "3[a2[c]]" decodes to "accaccacc" because a2[c] becomes acc, then that whole block repeats three times.

Input / output

• Input: s: string
• Output: decoded string

Examples

1. s = "3[a]2[bc]" returns "aaabcbc".
2. s = "3[a2[c]]" returns "accaccacc".
3. s = "2[abc]3[cd]ef" returns "abcabccdcdcdef".

Constraints

• 1 <= s.length <= 30
• s consists of lowercase English letters, digits, and square brackets.
• s is a valid encoding.
• The decoded output length is at most 10^5.

Hints

1. When you enter a [ group, you need to remember both the string built so far and the repeat count that applies to the new nested substring.
2. A recursive parser can return both the decoded substring and the index where the matching ] was found.

Follow-up How would you solve this iteratively with an explicit stack instead of recursion?