Decode String Stack

Use a stack to expand a run-length encoded string with nested patterns.

stacks string parsing

Write a function `decode_string(s: str) -> str` that takes a compressed string `s` and returns the fully decoded string. The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is repeated exactly `k` times. `k` is a positive integer. The input is guaranteed to be well-formed — no missing brackets or invalid characters. Nested encodings are possible, and the decoded string will not exceed 10^5 characters.

Constraints

• 1 <= len(s) <= 1000
• s consists of digits, lowercase English letters, and brackets '[' and ']'.
• k is a positive integer and will not have leading zeros.
• The decoded string length ≤ 100000.
• You may assume the input is always valid.

Example

>>> decode_string('3[a]2[bc]')
'aaabcbc'
>>> decode_string('3[a2[c]]')
'accaccacc'
>>> decode_string('2[abc]3[cd]ef')
'abcabccdcdcdef'

25 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use two stacks: one for numbers and one for previous strings.

When you see a digit, accumulate the full number (it may be multiple digits).

When you see ']', pop the last number and last string, then repeat the current string and attach it to the popped string.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.