# Longest Palindromic Substring

## 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 = 0i < ni++)
for (int j = 0j < nj++)
dp[i][j] = false;

int ans = 1;

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

for (int length = 2length <= nlength++)
{
for (int i = 0i <= n – lengthi++)
{
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(anslength);
}
}

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

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

### Output

`kabcdcbaqxaba7Explanation - abcdcba is the longest palindromic substring.`