Longest Palindromic Substring

December 7, 2021

Longest Palindromic Substring

In the longest palindromic substring problem we have to find the length of longest substring of the given string which is a palindrome. It is a famous interview question asked in many coding interviews as well as coding rounds. In this article, we will be explanation solution with c++ code.

Longest Palindromic Substring Problem Description

In this problem we are given a input string consisting of english alphabets. We have to return the length a longest palindromic substring possible. A substring is a string that is formed by removing any number of characters (including 0) from the input string from front or back.

Input:

Single line input containing an input string.

Output:

Longest length required.

Longest Palindromic Substring Solution

The problem is similar to longest palindromic substring with little changes.

Algorithm

Create a dp table (boolean type) where if dp[i][j] is true this implies substring[i…j] is a palindrome.
The dp transitions will be –

if(s[i] == s[j] && substring s[i+1…j-1] is palindrome)

dp[i][j] = true (ie it also palindrome)

We will fill base case ie mark all 1 character length substrings in dp table as palindrome.
We will iterate for all possible lengths of substrings and use above formulae.

Time & Space Complexity – O(N*N), where N = length of input string.

Code

#include <bits/stdc++.h>
using namespace std;
int f(string s)
{
    int n = s.length();
    bool dp[n][n];

    // Initializing dp table
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = false;

    int ans = 1;

    // All single characters are palindromes
    for (int i = 0; i < n; i++)
        dp[i][i] = true;

    for (int length = 2; length <= n; length++)
    {
        for (int i = 0; i <= n – length; i++)
        {
            int j = i + length – 1;
            if (length == 2) 
            {
                if (s[i] == s[j])
                    dp[i][j] = true;
            }
            else
            {   
                /*
                    For substring[i…j]
                    If(s[i]==s[j])
                        and substring[i+1…j-1] is also a palindrome
                        => substring[i…j] is also a palindrome 
                */
                
                if (s[i] == s[j] && dp[i + 1][j – 1])
                    dp[i][j] = true;
            }

            if (dp[i][j])
                ans = max(ans, length);
        }
    }

    return ans;
}
int main()
{
    string s;
    cin >> s;

    cout << f(s) << endl;
    return 0;
}

Output

kabcdcbaqxaba
7
Explanation - abcdcba is the longest palindromic substring.