Encode String with Shortest Length

This page explains Java solution to problem Encode String with Shortest Length using Dynamic Programming algorithm.

Problem Statement

Given a non-empty string, encode the string such that its encoded length is the shortest.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.

• k will be a positive integer.
• If an encoding process does not make the string shorter, then do not encode it. If there are several solutions, return any of them.

Input: s = "aaaaa"
Output: "5[a]"
Explanation: "5[a]" is shorter than "aaaaa" by 1 character.

Input: s = "abbbabbbcabbbabbbc"
Output: "2[2[abbb]c]"
Explanation: "abbbabbbc" occurs twice, but "abbbabbbc" can also be encoded to "2[abbb]c", so one answer can be "2[2[abbb]c]".

Solution

package com.vc.hard;

class EncodeStringWithShortestLength {
    public String encode(String s) {
        if(s == null || s.length() == 0) return "";

        int n = s.length();
        String[][] dp = new String[n][n];
        for(int len = 0; len < s.length(); len++) {
            for(int from = 0; from + len < s.length(); from++) {
                int to = from + len;

                String subStr = s.substring(from, to + 1);
                dp[from][to] = subStr;

                if(to - from < 4) continue;

                //See if length is less if we combine two half
                for(int middle = from; middle < to; middle++) {
                    int length = (dp[from][middle] + dp[middle + 1][to]).length();
                    if(length < dp[from][to].length()) {
                        dp[from][to] = dp[from][middle] + dp[middle + 1][to];
                    }
                }

                //See if we can find any repeat String
                int index = (subStr + subStr).indexOf(subStr, 1);

                if(index < subStr.length()) {
                    subStr = subStr.length() / index + "["+dp[from][from + index - 1]+"]";
                }

                if(subStr.length() < dp[from][to].length()) {
                    dp[from][to] = subStr;
                }
            }
        }
        return dp[0][n - 1];
    }
}

Time Complexity

O(N³) Where
N is length of input string

Space Complexity

O(N²) Where
N is length of input string