# Accepted Solution in Java

• This is the first question I have answered in Leetcode. I hope you guys will like my solution. The approach here is simple. We will form 2-D array of Strings.
dp[i][j] = string from index i to index j in encoded form.

We can write the following formula as:-
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]) or if we can find some pattern in string from i to j which will result in more less length.

Time Complexity = O(n^3)

public class Solution {

`````` public String encode(String s) {
String[][] dp = new String[s.length()][s.length()];

for(int l=0;l<s.length();l++) {
for(int i=0;i<s.length()-l;i++) {
int j = i+l;
String substr = s.substring(i, j+1);
// Checking if string length < 5. In that case, we know that encoding will not help.
if(j - i < 4) {
dp[i][j] = substr;
} else {
dp[i][j] = substr;
// Loop for trying all results that we get after dividing the strings into 2 and combine the   results of 2 substrings
for(int k = i; k<j;k++) {
if((dp[i][k] + dp[k+1][j]).length() < dp[i][j].length()){
dp[i][j] = dp[i][k] + dp[k+1][j];
}
}

// Loop for checking if string can itself found some pattern in it which could be repeated.
for(int k=0;k<substr.length();k++) {
String repeatStr = substr.substring(0, k+1);
if(repeatStr != null
&& substr.length()%repeatStr.length() == 0
&& substr.replaceAll(repeatStr, "").length() == 0) {
String ss = substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]";
if(ss.length() < dp[i][j].length()) {
dp[i][j] = ss;
}
}
}
}
}
}

return dp[0][s.length()-1];
}
}``````

• Clean solution. President elect approved.

• Although I'm not entirely sure about the run time of your replaceAll call. The replaceAll could potentially take O(n) time? @StefanPochmann any idea about the complexity of this problem?

• Yeah. replaceAll() will take O(n) time, but substr.length()%repeatStr.length() == 0 reduces its chances to occur very frequently. If I was removing this condition, then it was getting TLE.

• Thats replace all is really clever

• Your solution is great! It's really helpful. I kinda stuck at how to split the string to get the pattern. After I saw how you do the DP part, I fixed my problem. Thx!

Here is the version of my code, really similar to yours. I changed the find pattern part use the KMP algorithm. Hope it's a little helpful :)

``````public class Solution {
public String encode(String s) {
if(s == null || s.length() <= 4) return s;

int len = s.length();

String[][] dp = new String[len][len];

// iterate all the length, stay on the disgnose of the dp matrix
for(int l = 0; l < len; l ++) {
for(int i = 0; i < len - l; i ++) {
int j = i + l;
String substr = s.substring(i, j + 1);
dp[i][j] = substr;
if(l < 4) continue;

for(int k = i; k < j; k ++) {
if(dp[i][k].length() + dp[k + 1][j].length() < dp[i][j].length()) {
dp[i][j] = dp[i][k] + dp[k + 1][j];
}
}

String pattern = kmp (substr);
if(pattern.length() == substr.length()) continue; // no repeat pattern found
String patternEncode = substr.length() / pattern.length() + "[" + dp[i][i + pattern.length() - 1] + "]";
if(patternEncode.length() < dp[i][j].length()) {
dp[i][j] = patternEncode;
}
}
}

return dp[0][len - 1];
}

private String kmp (String s) {
int len = s.length();
int[] LPS = new int[len];

int i = 1, j = 0;
LPS[0] = 0;
while(i < len) {
if(s.charAt(i) == s.charAt(j)) {
LPS[i ++] = ++ j;
} else if(j == 0) {
LPS[i ++] = 0;
} else {
j = LPS[j - 1];
}
}

int patternLen = len - LPS[len - 1];
if(patternLen != len && len % patternLen == 0) {
return s.substring(0, patternLen);
} else {
return s;
}
}
}
``````

• @DonaldTrump Glad to see president :)

• This post is deleted!

• for every divisor of the length of substr you perform an O(n) replaceAll. why is it O(n) then?

• Excellent solution !

• A different way to fill the dp array, column by column, 33ms, beats 99%.
It is O(n^4). Yours is not O(n^3) either, replaceAll is not constant.

``````int n = s.length();
String[][] dp = new String[n][n];
for (int j = 0; j < n; ++j) {
int i = j;
dp[i][j] = s.substring(j, j+1);
for (int p = 0; p < i; ++p) {
dp[p][j] = dp[p][j - 1] + dp[i][j];
}
for (i = j - 1; i + 1 >= j - i; --i) {
String sub = s.substring(i + 1, j + 1); // s[i+1..j]
for (int k = i - (j - i) + 1; k >= 0 && sub.equals(s.substring(k, k + j - i)); k -= j - i) {
String str = Integer.toString((j + 1 - k) / (j - i)) + "[" + dp[i+1][j] + "]";
if (str.length() < dp[k][j].length()) {
dp[k][j] = str;
for (int p = 0; p < k; ++p) {
if (dp[p][k - 1].length() + str.length() < dp[p][j].length()) {
dp[p][j] = dp[p][k - 1] + str;
}
}
}
}
}
}
return dp[0][n-1];
``````

• Just a simple notice here:

``````// dp[i][k].length() + dp[k+1][j].length()
// is much faster than (dp[i][k] + dp[k+1][j]).length()
// because s1 + s2 is O(n) time, s1.length() + s2.length() is O(1) time
``````

• patternLen

Really nice idea of using KMP to find repeated pattern!

• @XiaotingHong I understand the part you built the LPS array.

But for this segment of the code , I could not understand . Could you give me some explanations.

int patternLen = len - LPS[len - 1];
if(patternLen != len && len % patternLen == 0) {
return s.substring(0, patternLen);
} else {
return s;
}

• @axieyangb

you can refer to the good explanation at http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/ which uses KMP to find repeated pattern.

• @axieyangb
That part is to find the repeated part.
For example, you have ABAB. Then LPS[len-1] = LPS[3] = 2
patternLen = 2, s.substring(0,2) = AB. So you find the minimum repeated part and return it.

• This post is deleted!

• This post is deleted!

• Notice that in int patternLen = len - LPS[len - 1];, so in your case, patternLen = 6 - 2 = 4. And 6 % 4 != 0, so the kmp() will return the string itself.

• @seaeidolon

You are right. My mistake.

Thank you!

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