# Problem of the day: Longest palindromic substring

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(N3).

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:

P(i, j) = true if i >= j else P(i+1, j-1) && S[i] == S[j]

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 > P(N+1, vector(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(N2) but it requires O(N2) 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(N2) 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(N2) solution is good enough for interview purposes.