# How to Solve Decode String

## Decode String Introduction

Decode String is a problem where a string of numbers and letters need to be decoded to reveal a hidden message. This is a common, albeit simplified, problem in cryptography, involving a multi-step approach and the application of recursion and additional data structures to improve time complexity.

## Decode String Problem

### Part 1 - Decode String Simplified

The simplified version of "decode string" presents us with an alpha-numeric string where a number may come before any letter. Given such a string, decode the string so that each number/letter combinations is expanded.

#### Example 1

input: `4a`  
output: `aaaa`

#### Example 2

input: `a2b10c`  
output: `abbcccccccccc`

### Part 2 - Decode String (Standard Version)

Given an encoded string `s`, return its decoded string.

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

**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]`.

#### Example 1

input: `abcdefg`  
output: `abcdefg`

#### Example 2

input: `ab2[c]3[de4[f]]`  
output: `abccdeffffdeffffdeffff`

#### Example 3

input: `2[2[2[a]]]`  
output: `aaaaaaaa`

## Decode String Solutions

There are two problems we will need to solve to successfully expand our string:

1. **Parsing** - We need to be able to walk through our input string and extract the counts and groupings.
2. **Groups within groups** - We need a way of tracking the nested structure of our encoded string.

The second issue is certainly related to parsing, but we will pull in some additional tools to manage it.

We will start with the simplified problem as a warmup exercise. This will give us a chance to get a feel for how parsing works. Once we have that under our belt we will move on to the more complex Leetcode version.

#### Approach to Simplified Problem

As a reminder, in this case, we have an alpha-numeric string where an integer may come before any alpha character. To solve this problem we will walk through our string one character at a time. We will use a string variable called `count` to store any digit information we encounter. We are using a string because we may need to store multiple digits and concatenating strings is trivial. Now each time we encounter an alpha character we can look at the count to determine the number of times that character should appear. After adding an alpha character, `count` will be reset.

In the python solution, we are using a bit of cleverness when it comes to multiplying count by char. Multiplying an integer `N` by a string `S` duplicates the string `N` times. In the javascript solution, we need to create a helper function to determine if a character is a digit.

#### Decode String Python, JavaScript and Java Solutions - Simplified Version

```python
def decode_string(s: str) -> str:
  solution_str = ""

# using a string to make our lives easier
  count = ""

for char in s:
    if char.isDigit():
      count += char
    else:
      if count == "":
        solution_str += char
      else:
        # multiplying a string by an int creates copies of the string!
        solution_str += int(count) * char
        count = ""

return solution_str
```

#### Time/Space Complexity

- Time complexity: `O(n)`, as we are iterating through our input string once and only applying `O(1)` operations throughout.  
- Space complexity: `O(10^n)`. The space complexity is a little harder to compute. For instance think about `9999a` (which we can think of as `(10^4-1)a`). We can see that the output string can quickly blow up in size. Because of this our worst-case space is `O(10^n)`.

#### Approach to Decode String - Standard Version (Recursion)

Now that we've warmed up using the simpler problem, let's tackle the more difficult problem!

In this more complex version our input string is different in two ways:

1. Now instead of using numbers to expand out a single character, a group of characters may be expanded out. Groups are defined by square brackets `[]`. For instance `3[ab]` would expand out to `ababab`. **Note**, any time there is a number, it is guaranteed to be followed by `[]`.
2. We are allowed to have groups inside of groups.

Similar to the previous solution we need to walk through our input string and categorize each character. Because we may have groups within groups, as we walk through our string we need a way of tracking which group we are currently parsing. We will introduce a new variable called `depth` to track this. When we first start parsing the string, `depth` will be `0`. Each time we step into a new group (when we encounter a `[`) `depth` will go up by one, and `depth` will go down by one each time we step out of a group (when we encounter a `]`). When `depth` returns to `0` we will know that we have processed an entire group.

#### Decode String Python, JavaScript and Java Solutions - Standard Version (Recursion)

```python
def decode_string(s: str) -> str:
  return_string = ""
  count = ""
  contents = ""
  depth = 0

for char in s:
    if depth == 0:
      if char.isdigit():
        count += char
      elif char == "[":
        depth += 1
      else:
        return_string += char
    else:
      if char == "]":
        depth -= 1

if depth == 0:
          # we found the end of a grouping
          # expand it and add it to our output string.
          return_string += int(count) * self.decode_string(contents)
          count = ""
          contents = ""
        else:
          contents += char
      else:
        if char == "[":
          depth += 1
        contents += char

return return_string
```

#### Time/Space Complexity

- Time complexity: `O(n^2)` due to our recursive calls.  
- Space complexity: `O(10^n)`

### Approach to Decode String - Standard Version (Stacks)

Now, our recursive solution has the weakness of needing to parse subgroups multiple times. For instance take the string `4[3[abc]3[xyz]]`. Our parser would walk over the entire string, then over `3[abc]3[xyz]`, then `[abc]`, and finally over `[xyz]`. This unnecessarily increases our time complexity!

In this approach, we are going to work on shaving some time off by processing groups as we parse. To do this we are going to create a stack. Each element of the stack represents a group. We will add elements to the stack as we encounter subgroups. Each time we finish parsing a group (encounter a `]`) we will pop it off the stack, expand it out, and add it to the new top element on the stack. Once all groups have been processed we will have only a single group in our stack. This is our final solution!

#### Decode String Python, JavaScript and Java Solutions - Standard Version (Stacks)

```python
class Encoding:
    def __init__(self, count:str = "", contents:str = "") -> None:
        self.count = count
        self.contents = contents

def decode_string(s: str) -> str:
    encoding_stack = [Encoding()]
    count = ""

for char in s:
        if char.isdigit():
            count += char
        elif char == "[":
            encoding_stack.append(Encoding(count=count, contents=""))
            count = ""
        elif char == "]":
            encoding = encoding_stack.pop()
            expanded_encoding = int(encoding.count) * encoding.contents
            encoding_stack[-1].contents += expanded_encoding
        else:
            encoding_stack[-1].contents += char

return encoding_stack[0].contents
```

#### Time/Space Complexity

- Time complexity: `O(n)`. The time complexity for this is much nicer than the previous solution. We are parsing our input string a single time and doing `O(1)` operations throughout.
- Space complexity: `O(10^n)`.