Decode an encoded string where counts and brackets describe repeated substrings.
Problem
You are given an encoded string containing lowercase letters, digits, and square brackets. The string uses the format k[encoded_string], where the substring inside the brackets should be repeated k times.
The encoding can be nested, meaning an expanded substring may itself contain more encoded parts.
Return the fully decoded string.
Notes
kis always a positive integer.- Brackets are always well-formed.
- Letters outside brackets should remain in the output in the same order.
- The decoded result may be much larger than the input.
Input Format
- A single string
s. scontains lowercase English letters, digits, and the characters[and].- The input is a valid encoded expression.
Output Format
- Return the decoded string after expanding all repetitions and nested groups.
Constraints
- Encoded counts are positive integers.
- The decoded string length may be large; use a method that builds the result incrementally.
Example 1
Input
s = "3[a]2[bc]"
Output
"aaabcbc"
Explanation
a is repeated 3 times, and bc is repeated 2 times. Concatenate the results: aaa + bcbc = aaabcbc.
Example 2
Input
s = "3[a2[c]]"
Output
"accaccacc"
Explanation
First decode the inner part 2[c] as cc, then expand a2[c] to acc, and finally repeat it 3 times.
Show 1 more example
Example 3
Input
s = "2[abc]3[cd]ef"
Output
"abcabccdcdcdef"
Explanation
Expand each bracketed segment and keep the trailing characters ef unchanged.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.