## The challenge

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; 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 won’t be input like `3a` or `2[4]`.

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

Example 4:

```Input: s = "abc3[cd]xyz"
Output: "abccdcdcdxyz"```

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

## Let’s start by writing some Test cases

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 `````` ``````import org.junit.jupiter.api.Test; import static org.junit.jupiter.api.Assertions.*; class DecodeStringTest { DecodeString ds = new DecodeString(); @Test void decodeString1() { String actual = ds.decodeString("3[a]2[bc]"); String expected = "aaabcbc"; assertEquals(expected, actual); } @Test void decodeString2() { String actual = ds.decodeString("3[a2[c]]"); String expected = "accaccacc"; assertEquals(expected, actual); } @Test void decodeString3() { String actual = ds.decodeString("2[abc]3[cd]ef"); String expected = "abcabccdcdcdef"; assertEquals(expected, actual); } @Test void decodeString4() { String actual = ds.decodeString("abc3[cd]xyz"); String expected = "abccdcdcdxyz"; assertEquals(expected, actual); } } ``````

This is all pretty simple, nothing onerous here so far.

## The solution in Java code

At first we could try and knock out something like the following:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `````` ``````public class DecodeString { public String decodeString(String s) { StringBuilder sb = new StringBuilder(); for (int i=0; i

BUT! When we run this against our test cases, we’ll notice the following:

 ``````1 2 3 `````` ``````org.opentest4j.AssertionFailedError: Expected :accaccacc Actual :a2ca2ca2c] ``````

This is because test-case number 2 makes our lives a little harder by requiring a wrapped expression:

So attempt number 2 at this solution would be to approach the problem from the perspective of a `stack`:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 `````` ``````import java.util.Stack; public class DecodeString { public String decodeString(String s) { Stack freqStack = new Stack<>(); Stack strStack = new Stack<>(); StringBuilder currStr = new StringBuilder(); int k =0; for(char c : s.toCharArray()){ if(Character.isDigit(c)){ k = k*10 + (c-'0'); } else if (Character.isLetter(c)){ currStr.append(c); } else if(c == '['){ freqStack.push(k); strStack.push(currStr); k =0; currStr = new StringBuilder(); } else if(c == ']'){ StringBuilder temp = currStr; int freq = freqStack.pop(); currStr = strStack.pop(); while(freq-->0){ currStr.append(temp); } k = 0; } } return currStr.toString(); } } ``````