This page explains Java solution to problem `Encode String with Shortest Length`

using `Dynamic Programming`

algorithm.

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

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

O(N

^{3}) Where

N is length of input string

O(N

^{2}) Where

N is length of input string