Problem of the day for today is Longest palindromic substring: *Given a string, find its longest palindromic substring.*. For example, given the string “ababab”, the longest palindromic substring would be “ababa”.

The obvious brute-force solution is to check each substring for being a palindrome. In a string of length N, since there are only N*(N+1)/2 substrings and checking each of them takes at most O(N) time, the overall time complexity is O(N^{3}).

It’s easy to see that the brute-force solution is doing a lot of repeated computation. If S[3..4] is not a palindrome, then S[2..5] and S[1..6] are not going to be palindromes and there’s no point in checking. Similarly, if S[3..4] is a palindrome, then for S[2..5] to be a palindrome, we need only check S[2] == S[5]. We can get rid of this repeated computation with the following dynamic programming formulation:

We can keep track of the largest palindromic length and its starting position, leading to the following simple implementation:

string longestPalindrome(string A) { | |

int N = A.size(); | |

vector<vector<bool> > P(N+1, vector<bool>(N+1, true)); | |

int start = 0, len = 1; | |

for (int k = 1; k < N; ++k) { | |

for (int i = 1; i <= N-k; ++i) { | |

P[i][i+k] = P[i+1][i+k-1] && (A[i-1] == A[i+k-1]); | |

if (P[i][i+k] && k+1 > len) | |

start = i-1, len = k+1; | |

} | |

} | |

string result(A.begin() + start, A.begin() + start + len); | |

return result; | |

} |

This reduces the time complexity to O(N^{2}) but it requires O(N^{2}) additional space.

There’s another clever way to think about this problem: Think of growing a palindromic substring from the center by expanding outwards if the characters on both sides match. We can determine the length of a palindromic substring situated at a given center in O(N) and there are only 2*(N-1) possible centers (one at each vertex and one between every two consecutive vertices). This will give us O(N^{2}) time complexity with no additional space requirement. Here’s the implementation:

int palindromeLengthFromCenter(string& A, int left, int right) { | |

int originalLeft = left; | |

while (left >= 0 && right < A.size() && A[left] == A[right]) { | |

left--; | |

right++; | |

} | |

return originalLeft - left; | |

} | |

string longestPalindrome(string A) { | |

int maxLen = 1, maxStart = 0; | |

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

int s1 = palindromeLengthFromCenter(A, i-1, i+1); // center is at position i | |

int len1 = 1 + 2 * s1; | |

if (len1 > maxLen) | |

maxLen = len1, maxStart = i - s1; | |

int s2 = palindromeLengthFromCenter(A, i, i+1); // center is between positions i and i+1 | |

int len2 = 2 * s2; | |

if (len2 > maxLen) | |

maxLen = len2, maxStart = i - s2 + 1; | |

} | |

string result(A.begin() + maxStart, A.begin() + maxStart + maxLen); | |

return result; | |

} |

This code is still doing some repeated computation. Consider the string “abababa”, once we have calculated the palindrome lengths centered at positions 1, 2, 3, 4 (1-based indexing), we can utilize the symmetry of palindromes around their center and no longer need to calculate the palindrome lengths for positions 5, 6, 7. This coupled with a few other tricks reduces the time complexity to O(N) in manacher’s algorithm. I think it’s too complicated to remember or derive on your own and O(N^{2}) solution is good enough for interview purposes.