> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Decode String Python Solution with Tests

> Tested Python solution for LeetCode 394 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 394, Medium. Topics: String, Stack, Recursion. [View on LeetCode](https://leetcode.com/problems/decode-string/description/).

Generate this problem as a practice environment: tested reference solution, 15 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 394   # by problem number
lcpy gen -s decode_string   # by problem name
```

## Problem

Given an encoded string, return its decoded string.

The encoding rule is: `k[encoded_string]`, where the `encoded_string` inside the square brackets is being repeated exactly `k` times. Note that `k` is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, `k`. For example, there will not be input like `3a` or `2[4]`.

The test cases are generated so that the length of the output will never exceed 10^5.

### Examples

```
Input: s = "3[a]2[bc]"
Output: "aaabcbc"
```

```
Input: s = "3[a2[c]]"
Output: "accaccacc"
```

```
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
```

### Constraints

* 1 \<= s.length \<= 30
* s consists of lowercase English letters, digits, and square brackets '\[]'
* s is guaranteed to be a valid input
* All the integers in s are in the range \[1, 300]

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/decode_string/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/decode_string/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(n) - single pass through string
    # Space: O(n) - stack storage for nested brackets
    def decode_string(self, s: str) -> str:
        """
        Decode string using stack for nested brackets.

        Example: s = "2[b3[a]]" → "baaabaaa"

        Process: 2 [ b 3 [ a ] ]

        char='2': num=2
        char='[': push('', 2), reset
        char='b': str='b'
        char='3': num=3
        char='[': push('b', 3), reset
        char='a': str='a'
        char=']': pop('b', 3) → str = 'b' + 'a'*3 = 'baaa'
        char=']': pop('', 2) → str = '' + 'baaa'*2 = 'baaabaaa'
        """
        stack = []
        current_str = ""
        current_num = 0

        for char in s:
            if char.isdigit():
                current_num = current_num * 10 + int(char)
            elif char == "[":
                # Push current state and reset
                stack.append((current_str, current_num))
                current_str = ""
                current_num = 0
            elif char == "]":
                # Pop and construct
                prev_str, repeat_count = stack.pop()
                current_str = prev_str + current_str * repeat_count
            else:
                current_str += char

        return current_str
```

## Complexity

| Time                              | Space                                    |
| --------------------------------- | ---------------------------------------- |
| O(n) - single pass through string | O(n) - stack storage for nested brackets |

## Tags

[Grind](/catalog/grind), [NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).