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:

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:

import java.util.Stack;

public class DecodeString {
    public String decodeString(String s) {
        Stack<Integer> freqStack = new Stack<>();
        Stack<StringBuilder> 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();
    }
}