Longest Palindromic Substring

Today we will discuss a common problem. The problem is, you are given a string S, you have to find the longest palindromic substring in S.
For example, S = abcbsd, here our desired answer is bcb with length 3.

Solution: This problem can be solved in many ways. One of them is DP solution and another is Expand Around Center.

DP: DP solution is a very straight cut solution. We go through all the substrings of the main string S and check each substring is palindrome or not and find the longest substring if it is palindrome. Here we do DP in the palindrome checking part. Here is the Code. Complexity O(n^2).

#include<bits/stdc++.h>
using namespace std;
 
string s;
int dp[1005][1005]; ///dp[l][r] means is substring s[l...r] is a palindrome or not
 
int isPalindrome(int left,int right)
{
    if( left >= right )
        return 1;
    if( dp[left][right] != -1 )
        return dp[left][right];
    int result = 0;
    if( s[left] == s[right] )
        result = isPalindrome(left+1 , right-1);
    return dp[left][right] = result;
}
 
int main()
{
    memset(dp , -1 , sizeof(dp));
    int n, mx = 0, start = 0;
    string ans;
    cin >> s;
    n = (int)s.size();
 
    for(int i=0 ; i<n ; i++){
        for(int j=i ; j<n ; j++){
            if(mx < j-i+1 && isPalindrome(i,j))
            {
                mx = j-i+1;
                start = i;
            }
        }
    }
    ans = s.substr(start, mx);
    cout << ans << endl;
    return 0;
}
 

Expand Around Center: This solution is based on the center of the palindrome string. We observe that a palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2n − 1 such centers. Complexity O(n^2). The code is right below.

#include<bits/stdc++.h>
using namespace std;
 
int extendPalindrome(string &s, int l, int r)
{
    while(l >= 0 && r <s.size() && s[l] == s[r] )
    {
        l--; r++;
    }
    return r-l-1;
}
int main()
{
    string s;
    cin >> s;
    bool even = 0;
    int Max = 0, num, n = (int) s.size()-1;
    for(int i = 0; i < n; i++)
    {
        int len1 = extendPalindrome(s,i,i);
        int len2 = extendPalindrome(s,i,i+1);
        int tmp = max(len1 , len2);
        if(Max < tmp)
        {
            Max = tmp;
            if( len1 >= len2 ) // odd palindrome
            {
                num = i;
                even = 0;
            }
            else // even palindrome
            {
                num = i;
                even = 1;
            }
        }
    }
    string ans = "";
    if(even)
    {
        int len = Max;
        Max /=2;
        ans =  s.substr(num- Max+1, len);
    }
    else
    {
        int len = Max;
        Max /=2;
        ans =  s.substr(num - Max, len);
    }
    cout << ans << endl;
    return 0;
}