LeetCode 394: Decode String

Problem Restatement

We are given an encoded string s.

The encoding rule is:

k[encoded_string]

This means encoded_string should be repeated exactly k times.

For example:

"3[a]" -> "aaa"
"2[bc]" -> "bcbc"

The encoding may be nested:

"3[a2[c]]" -> "accaccacc"

The input is guaranteed to be valid. Brackets are well-formed, repeat counts are positive integers, and digits only appear as repeat counts. The decoded output length will not exceed 10^5.

Input and Output

Example function shape:

def decodeString(s: str) -> str:
    ...

Examples

Example 1:

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

Decode each part:

3[a]  -> aaa
2[bc] -> bcbc

So the answer is:

"aaabcbc"

Example 2:

s = "3[a2[c]]"

Decode the inner part first:

2[c] -> cc

So:

a2[c] -> acc

Then repeat it three times:

3[acc] -> accaccacc

The answer is:

"accaccacc"

Example 3:

s = "2[abc]3[cd]ef"

Decode:

2[abc] -> abcabc
3[cd]  -> cdcdcd
ef      -> ef

The answer is:

"abcabccdcdcdef"

First Thought: Recursive Parsing

Because brackets can be nested, recursion is natural.

When we see k[...], we decode what is inside the brackets, then repeat it k times.

This works, but recursive parsing needs careful index management.

A stack gives the same behavior iteratively.

Key Insight

When we enter a bracket, we need to remember two things:

1. The string built before this bracket.
2. The repeat count before this bracket.

For example:

s = "3[a2[c]]"

When we reach [ after 3, we need to save:

previous string = ""
repeat count = 3

Then we start building the inside string.

When we later reach [ after 2, we save:

previous string = "a"
repeat count = 2

When we see ], we finish the current bracket level, repeat the current string, and attach it to the previous string.

So we use two stacks:

Algorithm

Initialize:

count_stack = []
string_stack = []
current = ""
number = 0

Scan the string character by character.

If the character is a digit:

number = number * 10 + int(ch)

This handles multi-digit counts like 12[a].

If the character is [:

1. Push number onto count_stack.
2. Push current onto string_stack.
3. Reset number = 0.
4. Reset current = "".

If the character is ]:

1. Pop the repeat count.
2. Pop the previous string.
3. Set:

   current = previous + current * repeat

If the character is a lowercase letter, append it to current.

At the end, return current.

Correctness

The variable current stores the decoded string for the current bracket level.

When the parser reads normal letters, appending them to current is correct because letters decode to themselves.

When the parser reads a number, it builds the repeat count for the next bracket. Multiplying the previous number by 10 before adding the new digit correctly handles multi-digit counts.

When the parser reads [, a new nested level begins. The algorithm saves the previous decoded prefix and the repeat count. Then it resets current so the inside of the bracket can be decoded independently.

When the parser reads ], the current nested level is complete. The correct decoded value of that level is current * repeat. This value belongs after the saved previous string, so previous + current * repeat restores the parent level correctly.

Because the input brackets are valid, every closing bracket matches the most recent opening bracket. The stack order therefore matches the nesting structure. After the full scan, current contains the fully decoded string.

Complexity

Let m be the length of the decoded output.

The encoded input length is small, but the decoded output may be much larger.

Implementation

class Solution:
    def decodeString(self, s: str) -> str:
        count_stack = []
        string_stack = []

        current = ""
        number = 0

        for ch in s:
            if ch.isdigit():
                number = number * 10 + int(ch)

            elif ch == "[":
                count_stack.append(number)
                string_stack.append(current)

                number = 0
                current = ""

            elif ch == "]":
                repeat = count_stack.pop()
                previous = string_stack.pop()

                current = previous + current * repeat

            else:
                current += ch

        return current

Code Explanation

The two stacks store saved parser state:

count_stack = []
string_stack = []

current stores the decoded string for the current nesting level:

current = ""

number stores the repeat count currently being read:

number = 0

For digits:

number = number * 10 + int(ch)

This parses counts like 10, 25, or 300.

When we see [, we save the current state:

count_stack.append(number)
string_stack.append(current)

Then reset for the nested string:

number = 0
current = ""

When we see ], we finish the current nested string:

repeat = count_stack.pop()
previous = string_stack.pop()

Then attach the repeated part to its parent:

current = previous + current * repeat

Letters are added directly:

current += ch

Finally:

return current

Testing

def test_solution():
    s = Solution()

    assert s.decodeString("3[a]2[bc]") == "aaabcbc"
    assert s.decodeString("3[a2[c]]") == "accaccacc"
    assert s.decodeString("2[abc]3[cd]ef") == "abcabccdcdcdef"
    assert s.decodeString("abc3[cd]xyz") == "abccdcdcdxyz"
    assert s.decodeString("10[a]") == "aaaaaaaaaa"
    assert s.decodeString("2[3[a]b]") == "aaabaaab"
    assert s.decodeString("1[z]") == "z"

    print("all tests passed")

test_solution()

Test meaning: