Program to find Longest palindromic Substring

December 20, 2021

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

C++ Code :-

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 : amaprep
The longest palindromic substring of amaprep is ama

Enter the string : prepinsta
The 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 : prepama
The longest palindromic substring of ama is 3

Enter the string : roota
The longest palindromic substring of oo is 2