# Program to find Longest palindromic Substring

## Longest palindromic Substring

Today in this article we will learn how to Write a program to find the longest Palindrome in a string.( Longest palindromic Substring ).

A string is palindrome if the reverse and the original string is same and here we need to find longest substring that is palindrome. Let’s understand this with example

Lets understand this with the help of an example:-

• Input sting:- amaprep
• Longest palindromic substring:- ama ## Algorithm

• Take input from the user
•  Make a Function to find the longest palindromic substring in `O(n²)` time and `O(1)` space
• Consider the base case if the length of string is 0 then return str
• Declare two string max_str and curr_str( max_str stores the maximum length palindromic substring )
• Declare two integer max_length , curr_length
• Run a loop from i=0 to length of string, Consider every character of the given string as a midpoint and expand in both directions to find maximum length palindrome
• update maximum length palindromic substring if odd length palindrome has a greater length
• Find the longest even length palindrome with str[i] and str[i+1] as midpoints. Note that an even length palindrome has two midpoints.
• update maximum length palindromic substring if even length palindrome has a greater length ## Method 1

`  #include<iostream>  #include<string>  using namespace std;  // Expand in both directions of low and high to find maximum length palindrome  string expand(string str, int left, int right)  {   // run till str[left.right] is a palindrome   while (left >= 0 && right < str.length() && (str[left] == str[right])) {   left--, right++; // Expand in both directions  }  // return palindromic substring   return str.substr(left + 1, right - left - 1);  }  // Function to find the longest palindromic substring in O(n²) time and O(1) space  string PalindromicSubstring(string str)  {    // base case    if (str.length() == 0) {      return str;   }   // max_str stores the maximum length palindromic substring found so far   string max_str = "", curr_str;   // max_length stores the maximum length of palindromic substring found so far   int max_length = 0, curr_length;   // consider every character of the given string as a midpoint and expand in both directions to find maximum length palindrome   for (int i = 0; i < str.length(); i++)   {     // find the longest odd length palindrome with str[i] as a midpoint    curr_str = expand(str, i, i);    curr_length = curr_str.length();   // update maximum length palindromic substring if odd length palindrome has a greater length   if (curr_length > max_length)   {     max_length = curr_length;     max_str = curr_str;   }  // Find the longest even length palindrome with str[i] and str[i+1] as midpoints.   //Note that an even length palindrome has two midpoints.   curr_str = expand(str, i, i + 1);   curr_length = curr_str.length();  // update maximum length palindromic substring if even length palindrome has a greater length   if (curr_length > max_length)   {    max_length = curr_length;    max_str = curr_str;   }  }  return max_str; }  int main() {  string str ;  cout << "Enter the string : ";  getline(cin, str);   cout<<"The longest palindromic substring of " << str << " is " << PalindromicSubstring(str);  return 0; }`

## Output:-

`Enter the string : amaprepThe longest palindromic substring of amaprep is ama`
```Enter the string : prepinstaThe longest palindromic substring of prepinsta is p
```

## Method 2

• Another approach will be to run 3 nested for loop that will increase the time complexity to O(n³)
• The approach is simple run the outer two loops will pick all substrings one by one by fixing the corner characters
• The inner loop will check if the substring is palindrome or not

## Output:-

```  // C++ implementation
#include <bits/stdc++.h>
using namespace std;

bool pal(string temp){
string temp2=temp;
reverse(temp2.begin(),temp2.end());
return temp==temp2;
}
int main()
{
string s,ans="";
cout<<"Enter the string : ";   cin>>s;
for(int i=0;i<s.size();i++){
string temp="";  //Storing the substring in temp
for(int j=i;j<s.size();j++){
temp+=s[j];
if(pal(temp)==true){
if(ans.size()<temp.size())
{
ans=temp;
}
}
}
}
cout<<"The longest palindromic substring of "<<ans<<" is "<<ans.size(); return 0;
}```

## Output:-

`Enter the string : prepamaThe longest palindromic substring of ama is 3`
```Enter the string : rootaThe longest palindromic substring of oo is 2
```