Software Engineering

# How to Solve the “Decode a String” Challenge in Java

## 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#

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

``````public class DecodeString {
public String decodeString(String s) {

StringBuilder sb = new StringBuilder();

for (int i=0; i<s.length(); i++) {
if (Character.isDigit(s.charAt(i))) {
int timesToRepeat = Integer.parseInt(""+s.charAt(i));

StringBuilder repeats = new StringBuilder();
for (int j=++i; j<s.length(); j++) {
if (s.charAt(j)=='[') {
//start of group
} else if (s.charAt(j)==']') {
//end of group
break;
} else {
//has repeat character
repeats.append(s.charAt(j));
}
i++;
}
sb.append(repeats.toString().repeat(timesToRepeat));

} else {
sb.append(s.charAt(i));
}
}

return sb.toString();
}
}
``````

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

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