Decode String
The key idea
Brackets nest, so the most recently opened group must be finished first. A stack stores the partial string and repeat count from each enclosing level. On '[' you push the work in progress and start fresh; on ']' you pop the saved string and count, then attach the repeated current piece. This LIFO order handles arbitrary nesting without recursion.
Problem
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 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, and so on. Furthermore, the original data does not contain any digits, and digits are only used to indicate the repeat counts k. For example, there will not be input like 3a or 2[4].
Constraints
- 1 <= s.length <= 30
- s consists of lowercase English letters, digits, and square brackets '[]'
- s is guaranteed to be a valid input
- All integers in s are in the range [1, 300]
Examples
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
Input: s = "3[a2[c]]"
Output: "accaccacc"
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization