Skip to main content
DSA patterns

Decode String

mediumStack and queue

Problem statement

A string has been compressed with the rule k[text], which means "text repeated k times". k is a positive integer and can have more than one digit, and groups can be nested inside other groups. Letters outside any brackets are copied as they are.

Return the fully expanded string. You can assume the input is always well formed: brackets are balanced, every [ is directly preceded by its count, and digits only ever appear as counts.

Examples

Example 1

Input: s = "3[a]2[bc]"

Output: "aaabcbc"

Explanation: "a" three times gives "aaa", and "bc" twice gives "bcbc". They are joined in order.

Example 2

Input: s = "3[a2[c]]"

Output: "accaccacc"

Explanation: The inner group 2[c] gives "cc", so each outer copy is "acc". Repeating it three times gives "accaccacc".

Hints

Hint 1: The innermost group has no brackets inside it, so it can be expanded directly. Think about what happens if you keep expanding the innermost group over and over.

Approach

Optimal: Stack

Intuition

Read the string once from left to right and keep two things: current, the text of the group you are building, and count, the number you are reading. When you meet [, pause: push current and count on a stack and start an empty group. When you meet ], the group is finished: pop the paused text and count, and glue the finished group back as previous + current * count. The stack remembers paused work in the right order, so nesting takes care of itself. It is faster than the brute force because nothing is rebuilt from scratch: each piece is put together once, as soon as its group closes.

Steps

  1. Start with current = "", count = 0 and an empty stack.
  2. Digit: set count = count * 10 + digit, so 12[a] reads as twelve, not two.
  3. [: push (current, count), then reset current = "" and count = 0.
  4. ]: pop (before, k) and set current = before + current * k.
  5. Letter: add it to the end of current.
  6. At the end, current is the answer.

Dry run

s = "3[a2[c]]"

char action current count stack
3 read digit "" 3 []
[ push ("", 3), reset "" 0 [("", 3)]
a add letter "a" 0 [("", 3)]
2 read digit "a" 2 [("", 3)]
[ push ("a", 2), reset "" 0 [("", 3), ("a", 2)]
c add letter "c" 0 [("", 3), ("a", 2)]
] pop ("a", 2): "a" + "c" * 2 "acc" 0 [("", 3)]
] pop ("", 3): "" + "acc" * 3 "accaccacc" 0 []

Edge cases: a string with no brackets just collects letters in current. Letters before or after a group are kept because they live in before or in current.

Complexity

Time O(L · d) - Here L is the length of the decoded string and d is the nesting depth. We read each input character once, but the text inside a nested group is copied again at every level it sits inside. For typical inputs d is small, so this is close to linear in the output size.

Space O(L) - The stack holds the paused text and counts of every open group, and the current text can grow up to the length of the answer. Nothing else grows with the input. The final string is the answer itself.

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []      # (text built before this '[', repeat count for this group)
        current = ""
        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, k = stack.pop()
                current = before + current * k
            else:
                current += ch
        return current


if __name__ == "__main__":
    print('"' + Solution().decodeString("3[a]2[bc]") + '"')
    print('"' + Solution().decodeString("3[a2[c]]") + '"')
RecapThe whole problem in a few lines, for the night before
  • Spot it: nested patterns like 3[a2[c]]
  • Idea: stack: on '[' push the current string and the repeat count; on ']' pop them and repeat the current string that many times
  • Cost: O(n x repeat factors), roughly the length of the decoded output, O(n) space
  • Trap: the repeat count can have several digits (like 12), and brackets can be nested

Interview follow-ups

  • Reject malformed input such as 2[a or a] with a clear error instead of crashing.

    Check the rules while you scan. On ], if the stack is empty, raise an error such as "unexpected ] at index 1" (this catches a]). On [, require that a count was just read, otherwise raise "missing count before [". After the last character, if the stack is not empty, raise "missing ] for the group opened at index 1" (this catches 2[a). Use each language's usual exception: ValueError in Python, IllegalArgumentException in Java and std::invalid_argument in C++. The scan is still O(L), and the error message should always include the position.

  • The decoded string could be huge. How would you return only its length, or the character at position i, without building it?

    For the length, run the same stack scan but keep numbers instead of text. A letter adds 1 to the current length, [ pushes the length so far and the count, and ] sets the length to before + count * inner. This is O(L) time and O(depth) space. Use 64-bit integers or big integers, because the length can overflow. For the character at position i, first record the length of each group. Then walk the top level, and when i falls inside a group, replace it with i % inner_length and descend into that group. Repeat until you land on a letter. Each lookup costs O(L) at worst, and nothing is ever expanded.

Frequently asked questions

By the time you reach ], the digits are far behind you and other counts may have been read in between. Saving the count with the text you paused keeps each group's count paired with the right group. Without this, 2[a3[b]] would mix up the 2 and the 3.

Yes. Write a function that reads from a position until the matching ] and returns the expanded text and the next position. On a digit it reads the whole number, skips the [, calls itself for the inner text and repeats the result. The call stack plays the role of the explicit stack, so time and space are the same. Very deep nesting can hit the recursion limit, for example in Python.

It is a small parser with nesting, like expanding templated config, brace expansion in a shell (web-{01..03}), or nested placeholders in a deployment manifest. The stack of paused work is how those expanders handle nesting.

A count can have more than one digit, as in 10[a]. When you read "1" and then "0", the first digit is worth ten, so each new digit must shift the old value left by one place. Setting count = digit would read 10[a] as zero repeats.