Decode String
Task example: Decode String
Expand each k[body] into k copies of body, including nested groups. Preserve letters outside brackets. Return the decoded text. The input is valid, contains lowercase English letters, brackets and repeat counts from 1 to 300, and produces at most 100,000 characters.
s = "3[a2[c]]" → "accaccacc"
Decode 2[c] to cc first. Then repeat acc three times to get accaccacc.
Source task: LeetCode 394Repeated expansion: video explanation
s = "3[a2[c]]" → "accaccacc"
Prefer reading? Follow the steps below.
- Find the first closing bracket and the last opening bracket before it. Their body contains no unresolved groups, so it can be expanded now.
- Walk backward over all digits before the opening bracket to read the complete count. Replace count[body] with body repeated count times, keeping the prefix and suffix.
- Restart until no brackets remain. Plain letters already form their decoded result.
Time complexity · O(n(n + L))
Let n be encoded length and L decoded length. At most O(n) expansions each scan or rebuild up to O(n + L) characters: O(n(n + L)) is a worst-case upper bound.
Space complexity · O(n + L)
Intermediate strings and temporary slices occupy O(n + L) space. The original string is immutable.
Stack parsing: video explanation
s = "3[a2[c]]" → "accaccacc"
Prefer reading? Follow the steps below.
- Read characters left to right. Build a multi-digit count with count = count * 10 + int(char). Append ordinary letters to the current list.
- At [, save (current, count) on the stack and reset both. At ], pop the outer list and repeat count, extend it with current * repeat, and continue with that outer list.
- Join the final character list into the result. A stack closes the most recently opened group first, so nested repeats stay in the correct order.
The stack avoids repeated whole-input searches. This implementation still copies expanded characters at each nesting level, so single-pass parsing does not mean O(n) total time.
Time complexity · O(n + dL)
Let d be maximum nesting depth, or 1 when there are no groups. Parsing costs O(n); expansions may copy up to L characters at each level. Time complexity is O(n + dL), including the final join.
Space complexity · O(n + L)
Saved lists, stack frames, repeated blocks and the result require O(n + L) peak space. Appending to lists avoids repeatedly copying the entire prefix for each letter.