MediumStringStackRecursion

Decode String

1 approach, code in every language

You are given an encoded string that uses the format k[content], where the bracketed content is repeated exactly k times. Encodings can be nested, so a bracketed section may itself contain more k[content] pieces. Return the fully expanded, decoded string.

The input is always well formed: brackets are balanced, repeat counts are positive integers, and letters outside brackets simply appear as themselves. There are no stray digits that are not tied to a bracketed block.

Example 1

Input: s = "2[ab]3[c]"

Output: "ababccc"

"ab" repeats twice and "c" repeats three times, concatenated in order.

Example 2

Input: s = "2[a2[b]]"

Output: "abbabb"

The inner "2[b]" becomes "bb", giving "abb", and the outer count doubles that to "abbabb".

Constraints

1 ≤ s.length ≤ 30
s consists of lowercase English letters, digits, and square brackets
1 ≤ k ≤ 300 for every repeat count
The input is guaranteed to be a valid encoding

Stack of counts and partial strings

Sweep left to right, pushing the current string and repeat count when a bracket opens and folding the finished block back in when a bracket closes.

Loading animation…

Intuition

Nesting is what makes this tricky, and a stack is the natural tool for nesting. As we read characters we build up a current string. When we hit an opening bracket we must remember what we had before it plus the number that will multiply the upcoming block, so we push both and reset. On a closing bracket we pop the saved prefix and multiplier, expand the block we just finished, and attach it back. Digits may span several characters, so we accumulate them into a running number.

Algorithm walkthrough

1Maintain a current string buffer, a running number, and two stacks for saved strings and saved counts.
2For each digit, extend the running number as num = num * 10 + digit.
3On '[', push the current buffer and the running number, then reset both.
4On ']', pop the saved count k and saved prefix, and set the buffer to prefix followed by k copies of the buffer.
5For a letter, append it to the buffer; after the whole scan, the buffer holds the decoded string.

Implementation

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        cur = ""
        num = 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '[':
                stack.append((cur, num))
                cur = ""
                num = 0
            elif c == ']':
                prev, k = stack.pop()
                cur = prev + cur * k
            else:
                cur += c
        return cur

Time

O(N)

Space

O(N)

N is the length of the decoded output; each output character is produced once and the stacks hold at most the nesting depth plus buffered content.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Stacks & Queues

After the pattern

Now solve one you haven't seen.

Expand the Weave Pattern is our own problem on the technique behind Decode String: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free