# Algorithms Problem Solving: Decode String

This post is part of the Algorithms Problem Solving series.

## Problem description

This is the Decode String problem. The description looks like this:

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

.

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

.

## Examples

**Example 1:**

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

**Example 2:**

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

**Example 3:**

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

## Solution

One of the possible solutions I came up with was to use a stack data structure to handle the data within the brackets. The basic idea is to iterate through all characters for each character, verify if it's a number, a `]`

(closing bracket), or a normal string character (`[`

included).

To iterate through the entire string, we can use a `while`

with an index:

```
while (index < encodedString.length) {
index++;
}
```

To verify if the character is a number, I built a simple function:

```
const isNum = (char) => !isNaN(Number(char));
```

So if the character is a number, we push it to the stack. But the number can be more than just one digit, so we need to move to the next index until the character isn’t a number anymore.

```
if (isNum(char)) {
const number = [];
while (isNum(encodedString[index])) {
number.push(encodedString[index]);
index++;
}
stack.push(Number(number.join('')));
continue;
}
```

I created a `number`

array and push each number character into this list. After we get the whole number, we push it to the stack.

But if the character is a `]`

, we need to get the whole string that was inside the brackets and we do it by using the `pop`

method from the stack. We do it until it gets to the `[`

character. Then we can `pop`

it again to remove the `[`

character. And finally, repeat the string x times and push it to the stack.

```
if (char === ']') {
let str = '';
while (stack[stack.length - 1] !== '[') {
str = stack.pop() + str;
}
stack.pop();
stack.push(str.repeat(stack.pop()));
index++;
continue;
}
```

The `repeat`

method is very interesting. I didn’t know about this method, so I usually do a loop that works fine too:

```
const repeatedString = [];
const str = 'hey';
let num = 3;
while (num > 0) {
repeatedString.push(str);
num--;
}
repeatedString.join(''); // 'heyheyhey'
```

Using repeat is so much simpler and more convenient for this problem.

```
const str = 'hey';
const num = 3;
str.repeat(num); // 'heyheyhey'
```

And finally, if it isn't a `]`

and number, just push the character to the stack and increment the index:

```
stack.push(char);
index++;
```

The whole implementation looks like this:

```
const isNum = (char) => !isNaN(Number(char));
function decodeString(encodedString) {
const stack = [];
let index = 0;
while (index < encodedString.length) {
const char = encodedString[index];
if (isNum(char)) {
const number = [];
while (isNum(encodedString[index])) {
number.push(encodedString[index]);
index++;
}
stack.push(Number(number.join('')));
continue;
}
if (char === ']') {
let str = '';
while (stack[stack.length - 1] !== '[') {
str = stack.pop() + str;
}
stack.pop();
stack.push(str.repeat(stack.pop()));
index++;
continue;
}
stack.push(char);
index++;
}
return stack.join('');
}
```

## Resources

**newsletter**if you're enjoying this blog. ❤