DSA sheet · Stack · Expression evaluation pattern

Decode String: Stack & Recursion

This is the last problem of the expression evaluation pattern. A string like "3[a]2[bc]" is a compressed message: the number in front of a bracket says how many times to repeat what is inside. We have to expand it back to "aaabcbc". The teacher admits the brackets scared her the first time she saw it in college. The thing that unlocked it: a closing bracket ] is the only moment we can actually do something, and everything else is just "remember it for later". That "remember now, use later" is exactly what a stack is for. She solves it with one stack of characters, explains why the time depends on the decoded length (not the input length), and says people who like recursion can solve it that way too. This page covers her stack solution, then the classic two-stack version (one stack for counts, one for strings), and then the recursive version.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Stacks, brackets and strings from scratch
• Part A · The teacher's way: one stack of characters
• Part B · Two stacks: counts and strings
• Part C · Recursion: let the call stack do it
• Part D · Revision page

Part 0 · Stacks, brackets and strings from scratch

What is a stack?

A stack is a pile: you add on the top (push) and remove from the top (pop). Peek means looking at the top without removing it. The last thing pushed is the first thing popped: LIFO (Last In, First Out).

We draw a stack left = bottom, right = top. Popping or peeking an empty list raises IndexError, so always check st is non-empty before st[-1] when it could be empty. That check is exactly where the teacher's version needs a fix (Part A, Doubt 4).

Why brackets and stacks go together

Brackets nest: in 3[a2[c]] the inner 2[c] opens after the outer bracket but closes before it. The bracket that opened last is the first to close. That's LIFO again. So a stack naturally remembers "which bracket am I inside right now, and what was going on outside it?"

This problem is listed under expression evaluation because it works like a calculator: a number (the repeat count) and an operation (repeat) get applied to an operand (the string inside the brackets), and the result is used by the level outside.

Strings are immutable: build them in a list

In Java (and Python) a string can't be changed. s = s + "a" builds a brand-new string and copies everything each time. Doing that in a loop costs O(length) per step. The teacher uses Java's StringBuilder to avoid it. The Python equivalent: collect pieces in a list, then join once with "".join(parts). Also, "ab" * 3 gives "ababab" in one go.

Recursion in one paragraph

Recursion is a function calling itself on a smaller piece of the problem. Each call waits on Python's call stack until the inner call returns. So a recursive solution is secretly also a stack solution: the call stack plays the role our list played. Each nested bracket = one deeper call.

Part A · The teacher's way: one stack of characters

LeetCode 394

1The question in simple words

You get an encoded string. The rule is k[text]: the text inside the square brackets is repeated exactly k times. Brackets can be nested. Return the fully expanded string.

The input is always valid: brackets are balanced, digits only appear as repeat counts (never as letters to copy), and there's no 3a or 2[4].

2What the constraints tell us

• 1 ≤ s.length ≤ 30: the input is tiny. But don't judge the speed by this n. The output can be enormous.
• 1 ≤ k ≤ 300: a count can have up to 3 digits. So "read one digit" is wrong. We must read the whole number.
• Only lowercase letters, digits and [ ]. The input is valid.
• LeetCode promises the output length is at most 10⁵. That's the size that really decides the running time.

3Intuition: nothing can be decided until "]"

Walk through 3[a]2[bc] one character at a time and ask "can I do anything yet?"

• At 3: no, I don't know what to repeat yet.
• At [: no.
• At a: no, more letters might follow inside the bracket.
• At ]: yes! Now the bracket is complete. Everything between the matching [ and here is the text, and the number just before that [ is the count.

So the plan: push every character onto a stack until a ] shows up. At a ], walk backwards by popping: letters until [, then the [, then the digits. Expand, and put the result back.

She also notices that each closed bracket gives a finished part that won't be multiplied by anything to its right: 3[a] → part 1 = "aaa", 2[bc] → part 2 = "bcbc". The answer is just the parts joined in order.

4Building the logic

At "]", step 1: pop the letters

Pop until the top is [. Everything popped is the text inside. It comes out backwards (for "bc" we pop c, then b).

Step 2: throw away the "["

The [ is just a separator that marks where the text starts. We don't need it: pop it once.

Step 3: pop the number

Now the top of the stack holds the digits of the count. It could be 3, 13 or 113. They also come out backwards: for 113 we pop 3, then 1, then 1.

Step 4: expand and push it back

Repeat the text k times. Then the teacher pushes every character of the result back onto the stack. At the very end, the stack holds the whole answer, bottom to top, and we join it.

5Approach steps

1. For each character of s: if it's not ], push it.
2. If it is ]: pop letters until the top is [, and reverse them → text.
3. Pop the [.
4. While the stack is non-empty and the top is a digit, pop it. Reverse → k = int(digits).
5. Push every character of text * k back onto the stack.
6. At the end, join the stack from bottom to top. That's the answer.

6Code (Python)

class Solution:
    def decodeString(self, s: str) -> str:
        st = []
        for ch in s:
            if ch != ']':
                st.append(ch)                     # can't decide anything yet: remember it
                continue
            # ch == ']' : one bracket is complete
            letters = []
            while st[-1] != '[':                  # 1. the text inside, popped backwards
                letters.append(st.pop())
            letters.reverse()
            text = "".join(letters)

            st.pop()                              # 2. throw away the '['

            digits = []
            while st and st[-1].isdigit():        # 3. the count (FIX: stop at a non-digit)
                digits.append(st.pop())
            digits.reverse()
            k = int("".join(digits))

            st.extend(text * k)                   # 4. push the expansion back, char by char
        return "".join(st)

7Code line by line

8Dry run

Example 1: s = "3[a]2[bc]"

The middle picture is why "pop digits until empty" fails: right after the 2 the next item is "a", and we must stop there.

Example 2 (nested): s = "3[a2[c]]"

9Complexity & remember

• Time: the teacher's point is that it's linear in the decoded output length, not in len(s). More exactly, every bracket level re-pops and re-pushes the characters it contains, so the work is the output length times the nesting depth at worst. With an input of at most 30 characters, the depth is tiny (at most about 7 levels), so in practice it's O(output length), up to about 10⁵.
• Space: O(output length) for the stack, which ends up holding the whole answer.
• Building with a list + join (StringBuilder in Java) matters: repeated s = s + x would copy the growing string again and again.

Part B · Two stacks: counts and strings

Part A pops characters one by one and rebuilds strings and numbers backwards. A tidier stack version (the one you'll often see in interviews) keeps whole numbers and whole strings on two separate stacks, so nothing ever needs reversing. The teacher doesn't code this one in the video. It's the same idea as hers ("remember the outside, expand at ]"), organised differently.

1The question in simple words

Same question: expand k[text], with nesting.

2What the constraints tell us

• Counts go up to 300 → read multi-digit numbers while scanning forward: num = num * 10 + digit (forward order, so no reversal problem this time).
• Output up to 10⁵ characters → still linear in the output for shallow nesting.

3Intuition: save the outside world at every "["

Keep a variable cur: the string we're building at the current bracket level. When a [ opens, we're about to start a new, deeper level. Before going in, we save two things about the level we're leaving:

• the count num that applies to the bracket we're entering → count stack
• the text cur we had built so far at this level → string stack

Then reset cur = "" and num = 0 and build the inside. At ], the inside is complete: pop the saved count k and the saved outside text prev, and set cur = prev + cur * k. We're back at the outer level, with the expansion attached.

4Building the logic

5Approach steps

1. counts = [], strs = [], cur = "", num = 0.
2. Scan s and apply the table above to each character.
3. Return cur (after the last character, all brackets are closed and we're at the outermost level).

6Code (Python)

class Solution:
    def decodeString(self, s: str) -> str:
        counts = []                 # repeat count of each open bracket
        strs = []                   # text built BEFORE each open bracket
        cur = ""                    # text of the level we're in now
        num = 0
        for ch in s:
            if ch.isdigit():
                num = num * 10 + int(ch)
            elif ch == '[':
                counts.append(num)  # save the count for this bracket
                strs.append(cur)    # save the outside text
                cur = ""            # start the inside fresh
                num = 0
            elif ch == ']':
                k = counts.pop()
                prev = strs.pop()
                cur = prev + cur * k   # outside text + repeated inside
            else:
                cur += ch           # a letter
        return cur

cur += ch copies the string, but the strings here are short (each level's text) and LeetCode's limits are small. For very long texts you could keep cur as a list and join at the end.

7Code line by line

8Dry run: s = "3[a2[c]]", both stacks after every step

Read each pair of pictures side by side: the top of counts (red) and the top of strs belong to the same open bracket.

"3[a]2[bc]" in short: at the first [ push 3, ""; cur = "a"; at ] cur = "" + "aaa". At the next [ push 2, "aaa"; cur = "bc"; at ] cur = "aaa" + "bcbc" = "aaabcbc". Here the "aaa" waited safely in the string stack, which is exactly the teacher's "part 1" idea.

9Complexity & remember

• Time: O(output length × depth) at worst, because each closing bracket builds a new string of its expanded size. In practice it's linear in the output.
• Space: O(output length) for the strings, plus O(depth) entries in each stack.

Part C · Recursion: let the call stack do it

The teacher mentions that many people who know recursion solve this problem that way. It's correct, but in her experience recursive code is usually slower (each call has extra overhead), so she prefers the explicit stack. Here's how it works, so you can choose.

1The question in simple words

Same question. Now "inside a bracket" becomes "inside a recursive call".

2What the constraints tell us

• s has at most 30 characters, so the nesting depth is small → recursion depth is small, and Python's 1000-call limit is no worry.

3Intuition

The text inside a bracket is itself a smaller encoded string. So: "decode from position i until you hit the matching ]" is the same job as the whole problem, just smaller. When we see k[, we call ourselves to decode the inside, get back the inside's text, and repeat it k times. The call stack remembers the outside text and the count, exactly like the two stacks in Part B did.

4Building the logic

• The helper dfs(i) decodes starting at index i and returns two things: the decoded text, and the index where it stopped (the ] that ended it, or the end of s).
• Digit → build num. Letter → add to the result. [ → call dfs(i + 1), append inner * num, reset num, and continue after the returned ]. ] → this level is finished: return.

5Approach steps

1. dfs(i): parts = [], num = 0.
2. While i < len(s): digit → num; letter → parts.append; [ → (inner, i) = dfs(i + 1), parts.append(inner * num), num = 0; ] → return (join(parts), i). Then i += 1.
3. At the end of s, return (join(parts), i).
4. Answer = dfs(0)[0].

6Code (Python)

class Solution:
    def decodeString(self, s: str) -> str:
        n = len(s)

        def dfs(i):
            parts = []
            num = 0
            while i < n:
                ch = s[i]
                if ch.isdigit():
                    num = num * 10 + int(ch)
                elif ch == '[':
                    inner, i = dfs(i + 1)       # decode the inside; i is now at its ']'
                    parts.append(inner * num)
                    num = 0
                elif ch == ']':
                    return "".join(parts), i    # this bracket level is done
                else:
                    parts.append(ch)
                i += 1
            return "".join(parts), i            # reached the end of s (outermost level)

        return dfs(0)[0]

7Code line by line

8Dry run: s = "3[a2[c]]"

1. dfs(0): reads 3 → num = 3. At i = 1 sees [ → calls dfs(2) and waits.
2. dfs(2): reads "a" → parts = [a]. Reads 2 → num = 2. At i = 4 sees [ → calls dfs(5) and waits.
3. dfs(5): reads "c" → parts = [c]. At i = 6 sees ] → returns ("c", 6).
4. Back in dfs(2): appends "c" × 2 → parts = [a, cc]. i = 6 → i += 1 → 7, sees ] → returns ("acc", 7).
5. Back in dfs(0): appends "acc" × 3. i = 7 → 8 = n, loop ends → returns ("accaccacc", 8). Answer accaccacc ✓

Compare with Part B: each waiting frame holds a (num, parts) pair, exactly what the counts and strs stacks held.

9Complexity & remember

• Time: same order as Part B, linear in the output for shallow nesting. Function calls add a constant overhead, which is the teacher's reason for preferring the stack.
• Space: O(output length) for the strings, plus O(depth) call frames.

Part D · Revision page

s = Solution()
print(s.decodeString("3[a]2[bc]"))       # aaabcbc
print(s.decodeString("3[a2[c]]"))        # accaccacc
print(s.decodeString("2[abc]3[cd]ef"))   # abcabccdcdcdef
print(s.decodeString("abc"))             # abc
print(s.decodeString("10[a]"))           # aaaaaaaaaa
print(s.decodeString("2[2[2[x]]]"))      # xxxxxxxx

Based on this video: Decode String