one way to solve it is to use DP. runtime is O(n^2) and it requires O(n)
extra space.
import java.util.ArrayList;
import java.util.List;
public class StringOperation {
public static void main(String[] args) {
StringOperation strOp = new StringOperation();
System.out.println(strOp.findLongRepeatedString("banana"));
System.out.println(strOp.findLongRepeatedString("aaaaa"));
}
public String findLongRepeatedString(String src) {
Result longestResult = null;
List repeatedStrs = new ArrayList();
for(int i = 1; i < src.length(); i++) {
List newRepeatedStrs = new ArrayListResult>();
for (Result result : repeatedStrs) {
if(src.charAt(result.endIndex+1) == src.charAt(i)) {
Result r = new Result();
r.startIndex = result.startIndex;
r.endIndex = result.endIndex+1;
newRepeatedStrs.add(r);
if(longestResult == null) {
longestResult = r;
} else if(r.length() > longestResult.length()) {
longestResult = r;
}
}
}
for(int j = 0; j < i; j++) {
if(src.charAt(j) == src.charAt(i)) {
Result r = new Result();
r.startIndex = j;
r.endIndex = j;
newRepeatedStrs.add(r);
if(longestResult == null) {
longestResult = r;
}
}
}
repeatedStrs = newRepeatedStrs;
}
if(longestResult == null) {
return null;
} else {
return src.substring(longestResult.startIndex, longestResult.
endIndex + 1);
}
}
private class Result {
private int startIndex;
private int endIndex;
public int length() {
return endIndex - startIndex;
}
}
}
