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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s