Decode String

Q: Why does the stack store the text that came before each bracket?

When a [ opens, the text decoded so far at that level is not finished: the group's copies still have to go after it. Pushing it keeps it safe while you decode the body from an empty string. When the matching ] arrives, popping gives that text back and you append the copies to it.

MediumStack Recursion

+10

An encoded string writes repeated text as k[text], which stands for text written k times in a row. Groups can sit inside other groups, so 2[a3[b]] stands for abbbabbb. Write a function that gets an encoded string s and returns the decoded string.

Letters outside every bracket stay as they are. Each count is a positive whole number written right before its [, and digits appear nowhere else.

Function

decodeString(s: string) → string

sstring: the encoded string
Returnsstring: the decoded string

Constraints

1 ≤ s.length ≤ 10⁴
s contains only lowercase English letters, digits, [ and ].
s is a valid encoding: every [ follows a count and has a matching ], and no brackets are empty.
Every count k satisfies 1 ≤ k ≤ 300 and has no leading zero.
Brackets nest at most 100 levels deep.
The decoded string has at most 5 × 10⁴ characters.

Examples

Input: s = "2[ab]3[c]x"
Output: "ababcccx"
Explanation: 2[ab] gives abab and 3[c] gives ccc. The x sits outside every bracket, so it is copied as it is, which gives ababcccx.

Input: s = "2[x3[yz]]"
Output: "xyzyzyzxyzyzyz"
Explanation: Decode the inside first: 3[yz] is yzyzyz, so the outer group's body is xyzyzyz. Written twice, that is xyzyzyzxyzyzyz.

Input: s = "q10[w]e"
Output: "qwwwwwwwwwwe"
Explanation: The count is 10, read from two digits, so w appears ten times between q and e. Code that reads only the digit next to the [ would repeat it 0 times.

+22 hidden tests on Submit

Follow-up

The decoded string can be far longer than the input. How would you return only the character at position i of the decoded string, without building it, when the decoded length can reach 10^18?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

The count comes before the brackets, but you cannot write the copies until you know what is inside them, and the inside can hold more groups. So a group can only be expanded once every group inside it is done. Each approach below is a way to finish the innermost groups first: rewrite the string from the inside out, let a recursive call finish the inner group before the outer one, or keep the unfinished outer groups on a stack. Below, n is the length of the input, m the length of the decoded string and d the deepest nesting.

Expand the innermost group, then repeat

Intuition

Decode the string the way you would on paper. Find a group with no other group inside it, write out its copies in place, and look again. In 2[x3[yz]], the group 3[yz] has nothing inside it, so the string becomes 2[xyzyzyz], and one more expansion gives the answer.

The first ] in the string always closes such a group. No other group has closed before it, so nothing between it and its [ can be a bracket. That [ is the nearest one to its left, and the count is the run of digits right before it. Replace the count, the brackets and the body with the body written k times, and repeat until no ] is left.

This is correct, but every expansion rebuilds the whole string. With b groups and a string that grows toward m characters, that is up to b × m character copies. The hidden test with about 1,300 groups side by side costs about 25 million copies to produce 27,688 characters, where one pass over the input would do.

Algorithm

Find the first ] in the string. If there is none, the string is decoded: return it.
Walk left from it to the nearest [. The text between them is the group's body.
Walk further left over the digits before that [ and read them as the count k.
Replace everything from the first digit to the ] with the body written k times.
Go back to step 1.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

Recursive descent

Intuition

The format is recursive: an encoded string is a sequence of letters and groups, and the body of a group is again an encoded string. So write one function, decode, that reads from a shared position until it reaches the ] that ends its level or the end of the input, and returns what it read, decoded.

When decode meets a digit, it reads the whole number, skips the [ and calls itself to decode the body. That call stops at the matching ], because any deeper ] was already consumed by a deeper call. The caller skips the ], appends the body k times and keeps reading. For 2[x3[yz]], the outer call reads 2; the next call reads x and 3; a third call returns yz; the middle call returns xyzyzyz; and the outer call writes it twice.

Each input character is read once. The real cost is copying: an output character is copied once for each group around it, so the time is O(n + m·d) for nesting depth d. The recursion also goes d calls deep. That is fine for 100 levels, but very deep input can overflow the call stack: Python, for one, stops at 1,000 nested calls by default.

Algorithm

Keep one position pos, shared by every call, starting at the first character.
decode() loops while pos is inside the string and not on a ].
On a letter, append it and move on.
On a digit, read the whole number k, skip the [, call decode() for the body, skip the ], and append the body k times.
Return what was built. The first call returns the decoded string.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

One pass with a stack

Intuition

The recursion keeps one unfinished piece of text per open group, inside its call frames. You can keep those pieces on a stack of your own instead and read the string in one loop.

Track two things for the current level: current, the text decoded so far, and count, the number being read. A digit extends count as count × 10 + digit, so 10 and 300 come out right. A [ opens a level: push current and count, then start both over. A letter goes onto current. A ] closes the level: pop the saved text and count, and current becomes the saved text followed by count copies of current.

Trace 2[x3[yz]]. At the first [ you push (empty, 2). The x makes current equal x. At the second [ you push (x, 3) and yz fills a fresh current. The first ] pops (x, 3), so current becomes xyzyzyz. The last ] pops (empty, 2), and current becomes xyzyzyzxyzyzyz.

Groups close in the reverse order they open, so the top of the stack is always the level the ] returns to. The work matches the recursion, O(n + m·d), but deep nesting only grows a list, never the call stack.

Algorithm

Start with an empty stack, an empty current and count = 0.
On a digit, set count = count × 10 + digit.
On [, push the pair (current, count), then reset current to empty and count to 0.
On a letter, append it to current.
On ], pop (before, k) and set current to before followed by k copies of current.
After the last character, return current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

Pitfalls and edge cases

Most wrong answers come from reading the count or from where the saved text goes.

Reading one digit as the whole count. In q10[w]e the count is 10. Code that takes only the digit before the [ repeats w 0 times.
Forgetting to reset count to 0 after pushing it. The next group's digits are then added onto the old number, so 2[a3[b]] reads its inner count as 23.
Putting the copies before the saved text. On a ] the result is the text before the group followed by the copies, so ab2[c] is abcc, not ccab.
Losing letters at the top level. The x in 2[ab]3[c]x is outside every bracket and still belongs in the answer.
Appending one character at a time to a long immutable string. Each append can copy the whole string, which turns a 50,000-character answer into billions of copies. Collect pieces in a list or a string builder.

Frequently asked questions4

What is the time complexity of Decode String?

Reading the input is O(n). Building the output copies each character once for every group it sits inside, so the total is O(n + m·d), where m is the decoded length and d the nesting depth. When every count is at least 2, each group is at most half as long as the group around it, so the copying stays under 2m. No approach can beat O(m), because the answer itself has m characters.

Should you solve Decode String with recursion or with a stack?

Both do the same work. Recursion follows the format directly, since a group's body is itself an encoded string, and it is often the fastest to write in an interview. The stack version does the same thing in one loop and keeps the unfinished outer levels in a list, so very deep nesting cannot overflow the call stack. If the interviewer asks about input nested thousands of levels deep, the stack is the answer.

How do you handle counts with more than one digit?

Build the number as you read it: start at 0 and, for each digit, set count = count × 10 + digit. When the [ arrives the number is complete, so 300[a] gives 300. Reset the count to 0 as soon as you push it, or the next group's digits are added onto it.

Why does the stack store the text that came before each bracket?

When a [ opens, the text decoded so far at that level is not finished: the group's copies still have to go after it. Pushing it keeps it safe while you decode the body from an empty string. When the matching ] arrives, popping gives that text back and you append the copies to it.

Python

def decodeString(s):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "2[ab]3[c]x"

Expected

"ababcccx"

Decode String

Function

Constraints

Examples

Hints

Solution

Expand the innermost group, then repeat

Recursive descent

One pass with a stack

Pitfalls and edge cases

Frequently asked questions4

Similar problems