Algorithm to get the longest Palindrome substring output from a table of size n

Question

The Longest Palindrome Substring, produces a table L [i, j] where L [i, j] is defined as 1 if the substring s [i, j] is a palindrome, and 0 otherwise. The table dimensions are n × n. Using the results of a DP table, describe an algorithm to output all palindrome substrings of maximum length, and justify its runtime of Θ(n 2 ). You must provide a general algorithm.

Answer 1

You didn't specify a language, so here's a DP implementation using C++:

vector<vector<int>> dp;

bool isPalindrome(string s, int start, int end) {

if (start > end) {

return true;

}

int dpval = dp[start][end];

if (dpval >= 0) {

return dpval == 1;

}

bool ret = s[start] == s[end] && isPalindrome(s, start+1, end-1);

dp[start][end] = ret ? 1 : 0;

return ret;

}

vector<string> longestPalindromeSubstrings(string s) {

int size = s.length();

dp = vector<vector<int>>(size, vector<int>(size, -1));

int maxLength = 1;

vector<string> results;

for (int i=0; i<size; i++) {

for (int j=i; j<size; j++) {

if (isPalindrome(s, i, j)) {

maxLength = max(maxLength, j-i+1);

}

}

}

for (int i=0; i<size; i++) {

for (int j=0; j<size; j++) {

if (dp[i][j] == 1 && j-i+1 == maxLength) {

results.push_back(s.substr(i, j-i+1));

}

}

}

return results;

}

The runtime is O(n²) because the DP table is n x n and each item in that table only needs to be calculated once and each calculation is O(1).

Also interesting to note that using DP isn't the most efficient algorithm here. I was able to get better performance using this code that doesn't use DP:

bool isPalindrome(string s, int start, int end) {

while (start < end) {

if (s[start] != s[end]) {

return false;

}

start++;

end--;

}

return true;

}

vector<string> longestPalindromeSubstrings(string s) {

int size = s.length();

int maxLength = 1;

vector<string> results;

for (int i=0; i<size-maxLength+1; i++) {

for (int j=size-1; j>=i+maxLength-1; j--) {

if (isPalindrome(s, i, j)) {

if (j - i + 1 > maxLength) {

maxLength = j - i + 1;

results.clear();

}

results.push_back(s.substr(i, j - i + 1));

break;

}

}

}

return results;

}