# Accepted DP-based solution

• Here is my accepted DP-based solution. Main idea is for each substring str[i ... j], the ending char str[j] can only fall into two cases:

1. it does not belong to any repeating pattern, i.e., not str[j] is not inside bracket "[]"
2. it belongs to some repeating pattern, i.e., str[j] is inside some bracket "[]"
As for case 2, I used List Array revIdx to store all the positions that certain char appears.

Any comment or feedback is welcome :)

Here is my code:

``````public class Solution {
public String encode(String s) {
// dp[i][j] = min (dp[i][j - 1] + 1, dp[i][m] + numOfDigits(k) + 2 + dp[m + 1][m + l])
//                              |-> str[j] is not inside "[]",   |-> str[j] is encoded, i.e. insides "[]"
/*
i ... m     m + 1 ... m + l     m + l + 1 ... m + 2l    ... ... ... m + (k - 1) * l + 1 ... m + k * l
|<-    l       ->|<-           l        ->| ...      |<-                     l           ->|
|<-                             k           times                                        ->|
here, m + k * l == j, s.substring(m + 1, m + l + 1) == ... == s.substring(m + (k - 1) * l + 1, m + k * l + 1)

Notice that k may NOT be the maximum repeated times
e.g. : "abcdefabcdefffffffffffffedcbafedcba"

also, k * l > numOfDigits(k) + 2 + l
*/
int len = s.length();
int[][] dp = new int[len + 1][len + 1]; // dp[i][j] = min encoded len for str[i ... j]
int[][][] bt = new int[len + 1][len + 1][2]; // bt[i][j][0] = len of repeated unit
// bt[i][j][1] = repeated times of unit
List<Integer>[] revIdx = new List[26];
for (int i = 0; i < 26; i++) {
revIdx[i] = new ArrayList();
}
for (int i = 0; i < len; i++) {
}
helper(s, 0, len - 1, revIdx, dp, bt);
StringBuilder sb = new StringBuilder();
genEncode(s, 0, len - 1, sb, dp, bt);
return sb.reverse().toString();
}
public void genEncode(String s, int start, int end, StringBuilder sb, int[][] dp, int[][][] bt) {
if (start > end) return;
if (bt[start][end][1] == 1) {
sb.append(s.charAt(end));
genEncode(s, start, end - 1, sb, dp, bt);
} else {
sb.append("]");
genEncode(s, end - bt[start][end][0] + 1, end, sb, dp, bt);
sb.append("[");
sb.append((new StringBuilder().append(bt[start][end][1])).reverse());
genEncode(s, start, end - bt[start][end][0] * bt[start][end][1], sb, dp, bt);
}
}
public int helper(String s, int start, int end, List<Integer>[] revIdx, int[][] dp, int[][][] bt) {
if (start > end) return 0;
if (dp[start][end] == 0) {
char endChar = s.charAt(end);
List<Integer> list = revIdx[endChar - 'a'];
int currIdx = Collections.binarySearch(list, end);
int minEncLen = helper(s, start, end - 1, revIdx, dp, bt) + 1; // ending char is not in any repeated pattern
int minEncUnitLen = 1;
int minEncTimes = 1;
for (int i = currIdx - 1; i >= 0; i--) { // repeat pattern str[list.get(i) ... end]
int prev = list.get(i);
if (prev * 2 < start + end - 1) {break;} // early termination
// end - list.get(i) <= list.get(i) - start + 1
String pattern = s.substring(prev + 1, end + 1);
int len = end - prev;
while (prev - len + 1 >= start && s.substring(prev - len + 1, prev + 1).equals(pattern)) {
prev -= len;
}
int k = (end - prev) / len; // max number of repeating unit
for (int t = 2; t <= k; t++) { // group all k units together may not be optimal
// e.g. "abcdefabcdefffffffffffffedcbafedcba"
int candEncLen = helper(s, start, end - len * t, revIdx, dp, bt) + getNumOfDigit(t) + 2 + helper(s, end - len + 1, end, revIdx, dp, bt);
if (candEncLen < minEncLen) {
minEncLen = candEncLen;
minEncUnitLen = len;
minEncTimes = t;
}
}
}
dp[start][end]= minEncLen;
bt[start][end][0] = minEncUnitLen;
bt[start][end][1] = minEncTimes;
//System.out.println("dp[" + start + "][" + end + "] = " + minEncLen);
//System.out.println("bt[" + start + "][" + end + "][0] = " + minEncUnitLen);
//System.out.println("bt[" + start + "][" + end + "][1] = " + minEncTimes);
}
return dp[start][end];
}
public int getNumOfDigit(int num) { // assume num > 0
int ret = 0;
while (num > 0) {
ret++;
num /= 10;
}
return ret;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.