# LeetCode 394: Decode String

## Problem Restatement

We are given an encoded string `s`.

The encoding rule is:

```text
k[encoded_string]
```

This means `encoded_string` should be repeated exactly `k` times.

For example:

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

The encoding may be nested:

```python
"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

| Item | Meaning |
|---|---|
| Input | An encoded string `s` |
| Output | The decoded string |
| Encoding rule | `k[encoded_string]` means repeat `encoded_string` `k` times |
| Nesting | Encoded strings may contain more encoded strings |
| Constraint | `1 <= s.length <= 30` |
| Constraint | `s` contains lowercase English letters, digits, and square brackets |
| Constraint | Every integer `k` is in `[1, 300]` |

Example function shape:

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

## Examples

Example 1:

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

Decode each part:

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

So the answer is:

```python
"aaabcbc"
```

Example 2:

```python
s = "3[a2[c]]"
```

Decode the inner part first:

```text
2[c] -> cc
```

So:

```text
a2[c] -> acc
```

Then repeat it three times:

```text
3[acc] -> accaccacc
```

The answer is:

```python
"accaccacc"
```

Example 3:

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

Decode:

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

The answer is:

```python
"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:

```python
s = "3[a2[c]]"
```

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

```text
previous string = ""
repeat count = 3
```

Then we start building the inside string.

When we later reach `[` after `2`, we save:

```text
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:

| Stack | Meaning |
|---|---|
| `count_stack` | Repeat counts before `[` |
| `string_stack` | Decoded string before `[` |

## Algorithm

Initialize:

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

Scan the string character by character.

If the character is a digit:

```python
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:
   ```python id="gmkmrt"
   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.

| Metric | Value | Why |
|---|---|---|
| Time | `O(m)` | The algorithm must create the decoded output |
| Space | `O(m)` | Stacks and current strings may store decoded parts |

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

## Implementation

```python
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:

```python
count_stack = []
string_stack = []
```

`current` stores the decoded string for the current nesting level:

```python
current = ""
```

`number` stores the repeat count currently being read:

```python
number = 0
```

For digits:

```python
number = number * 10 + int(ch)
```

This parses counts like `10`, `25`, or `300`.

When we see `[`, we save the current state:

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

Then reset for the nested string:

```python
number = 0
current = ""
```

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

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

Then attach the repeated part to its parent:

```python
current = previous + current * repeat
```

Letters are added directly:

```python
current += ch
```

Finally:

```python
return current
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"3[a]2[bc]"` | Multiple encoded groups |
| `"3[a2[c]]"` | Nested encoding |
| `"2[abc]3[cd]ef"` | Encoded groups plus plain suffix |
| `"abc3[cd]xyz"` | Plain prefix and suffix |
| `"10[a]"` | Multi-digit repeat count |
| `"2[3[a]b]"` | Nested group followed by letter |
| `"1[z]"` | Repeat count of one |