I am working on implementing the longest palindromic substring problem and I followed the approach with DP and extra O(N^2) (yes I know there is an even more efficient algorithm but I am not interested in that in this post).
My implementation which basically uses the recurrence:
P(i, j) = P(i + 1, j - 1) ^ s[i] == s[j]
builds the relevant table but the run time is much slower than expected.
It does give the correct output if I run it in my IDE after several seconds (15+) but it is rejected by any online judge as too slow. I am not sure where the issue is since I am using memorization. So there is not recomputation of the same cases.
The strings that are starting to show that the algorithm has a performance issue are over 900 chars long.
Update
I am updating the question to add full source code and test case
Dynamic Programming approach O(N^2) time and O(N^2) space (not accepted and too slow)
public static String longestPalindromeDP(String s) {
Map<List<Integer>, Boolean> cache = new HashMap<>();
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j < s.length(); j++) {
populateTable(s, i, j, cache);
}
}
int start = 0;
int end = 0;
for(int i = 0; i < s.length(); i++) {
for(int j = 0; j < s.length(); j++) {
if(cache.get(Arrays.asList(i, j))) {
if(Math.abs(start - end) < Math.abs(i - j)) {
start = i;
end = j;
}
}
}
}
return s.substring(start, end + 1);
}
private static boolean populateTable(String s, int i, int j, Map<List<Integer>, Boolean> cache) {
if(i == j) {
cache.put(Arrays.asList(i, j), true);
return true;
}
if(Math.abs(i - j) == 1) {
cache.put(Arrays.asList(i, j), s.charAt(i) == s.charAt(j));
return s.charAt(i) == s.charAt(j);
}
if(cache.containsKey(Arrays.asList(i, j))) {
return cache.get(Arrays.asList(i, j));
}
boolean res = populateTable(s, i + 1, j - 1, cache) && s.charAt(i) == s.charAt(j);
cache.put(Arrays.asList(i, j), res);
cache.put(Arrays.asList(j, i), res);
return res;
}
This is very slow in the populateTable but once it finishes the result is correct.
Brute force O(N^3) time and O(1) space: much faster and accepted
public static String longestPalindromeBruteForce(String s) {
if(s.length() == 1) {
return s;
}
String result = "";
for(int i = 0; i < s.length(); i++) {
for(int j = i + 1; j <= s.length(); j++) {
String tmp = s.substring(i, j);
if(isPalindrome(tmp)) {
if(tmp.length() > result.length()) {
result = tmp;
if(result.length() == s.length()) {
return result;
}
}
}
}
}
return result;
}
private static boolean isPalindrome(String s) {
for(int i = 0, j = s.length() - 1; i < j; i++, j--) {
if(s.charAt(i) != s.charAt(j)) {
return false;
}
}
return true;
}
Testing and input:
public static void main(String[] args) {
final String string1 = "civilwartestingwhetherthatnaptionoranynartionsoconceivedandsodedicatedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWehavecometodedicpateaportionofthatfieldasafinalrestingplaceforthosewhoheregavetheirlivesthatthatnationmightliveItisaltogetherfangandproperthatweshoulddothisButinalargersensewecannotdedicatewecannotconsecratewecannothallowthisgroundThebravelmenlivinganddeadwhostruggledherehaveconsecrateditfaraboveourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorlongrememberwhatwesayherebutitcanneverforgetwhattheydidhereItisforusthelivingrathertobededicatedheretotheulnfinishedworkwhichtheywhofoughtherehavethusfarsonoblyadvancedItisratherforustobeherededicatedtothegreattdafskremainingbeforeusthatfromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwhichtheygavethelastpfullmeasureofdevotionthatweherehighlyresolvethatthesedeadshallnothavediedinvainthatthisnationunsderGodshallhaveanewbirthoffreedomandthatgovernmentofthepeoplebythepeopleforthepeopleshallnotperishfromtheearth";
//final String string2 = "ibvjkmpyzsifuxcabqqpahjdeuzaybqsrsmbfplxycsafogotliyvhxjtkrbzqxlyfwujzhkdafhebvsdhkkdbhlhmaoxmbkqiwiusngkbdhlvxdyvnjrzvxmukvdfobzlmvnbnilnsyrgoygfdzjlymhprcpxsnxpcafctikxxybcusgjwmfklkffehbvlhvxfiddznwumxosomfbgxoruoqrhezgsgidgcfzbtdftjxeahriirqgxbhicoxavquhbkaomrroghdnfkknyigsluqebaqrtcwgmlnvmxoagisdmsokeznjsnwpxygjjptvyjjkbmkxvlivinmpnpxgmmorkasebngirckqcawgevljplkkgextudqaodwqmfljljhrujoerycoojwwgtklypicgkyaboqjfivbeqdlonxeidgxsyzugkntoevwfuxovazcyayvwbcqswzhytlmtmrtwpikgacnpkbwgfmpavzyjoxughwhvlsxsgttbcyrlkaarngeoaldsdtjncivhcfsaohmdhgbwkuemcembmlwbwquxfaiukoqvzmgoeppieztdacvwngbkcxknbytvztodbfnjhbtwpjlzuajnlzfmmujhcggpdcwdquutdiubgcvnxvgspmfumeqrofewynizvynavjzkbpkuxxvkjujectdyfwygnfsukvzflcuxxzvxzravzznpxttduajhbsyiywpqunnarabcroljwcbdydagachbobkcvudkoddldaucwruobfylfhyvjuynjrosxczgjwudpxaqwnboxgxybnngxxhibesiaxkicinikzzmonftqkcudlzfzutplbycejmkpxcygsafzkgudy";
long startTime = System.nanoTime();
String palindromic = longestPalindromeDP(string1);
long elapsed = TimeUnit.SECONDS.convert(System.nanoTime() - startTime, TimeUnit.NANOSECONDS);
System.out.println(elapsed);
System.out.println(palindromic);
}
The BruteForce finishes in 0 seconds.
The DynamicProgramming finishes in up to 9 seconds (depending on the machine)
What is the problem here?
I understand that there can be some optimization to improve the performance but how is it possible that the O(N^3) outperforms the O(N^2) since I use memoization?
Update
Update based on the answer of @CahidEnesKeleş
I replaced the List<Integer> as key with a custom object:
class IdxPair {
int i;
int j;
IdxPair(int i, int j) {
this.i = i;
this.j = j;
}
@Override
public boolean equals(Object o) {
if(o == null || !(o instanceof IdxPair)) return false;
if(this == o ) return true;
IdxPair other = (IdxPair) o;
return this.i == other.i && this.j == other.j;
}
@Override
public int hashCode() {
int h = 31;
h = 31 * i + 37;
h = (37 * h) + j;
return h;
}
}
Although a couple of test cases that previously failed, now pass it is still too slow overall and rejected by online judges.