Find Longest Palindromic Substring – SET 1

Longest Palindromic Substring” is important and one of the interview favorite problem of string data structure. Here, we are given a string and our task is to find the longest palindromic substring in the given string. 

Longest Palindromic Substring: Longest Palindromic Substring of the given string is a substring of the string which is palindrome also. We need to find the largest possible substring of that type.

If there is no palindromic substring of length greater than 1 present in the string, simple return first character of the string.

Example:

INPUT:
abcba
OUTPUT:
Longest Palindromic Substring: abcba
Explanation:
“abcba” is itself palindromic string.
INPUT:
abcded
OUTPUT:
Longest Palindromic Substring: ded
Explanation:
“ded” is the longest substring in the string “abcded” which is palindromic.

In this post, we will discuss the brute-force approach to get the solution. The steps required to find the longest palindromic substring are:

  1. Initialize an empty resultant  string.
  2. Generate all possible substring of the given string.
  3. For, every substring generated, check whether it is palindrome or not.
  4. If it is palindrome, check its length with resultant string length.
  5. If it’s greater, assign the resultant string with generated palindromic substring.

The time complexity of this solution is O(n^4) for generating all substring and check palindrome.

C++ Program to find the Longest Palindromic Substring in a given string is as follows:

#include<bits/stdc++.h>
using namespace std;
bool isPalindrome(string str)
{
    string temp = str;
    reverse(temp.begin(),temp.end());
    return (temp==str) ? true : false ;
}
void longestPalindrome(string str)
{
    // Single characterb is itself a palindrome
    string res = str.substr(0,1);
    //Generate all possible substrings of a given string
    for(int i = 0 ; i < str.length() ; i++)
    {
        for(int j = i ; j < str.length() ; j++)
        {
            string substring = "";
            for(int k = i ; k <= j ; k++)
            {
                substring = substring + str[k];
            }
            // check whether generated substring is palindrome or not
            bool checkPalindrome = isPalindrome(substring);
            // If palindrome, compare its length with resultant palindrome
            if(checkPalindrome)
            {
                if(substring.length() > res.length())
                res = substring;
            }
        }
    }
    cout<<"Longest Palindromic Substring: "<<res<<"\n";
}
int main()
{
    string str;
    
    /* Scan String */
    cout<<"Enter a string:\n";
    cin>>str;
    
    /* Function to find Longest Palindromic Substring */
    longestPalindrome(str);
}

OUTPUT:
Enter a string:
abcded
Longest Palindromic Substring: ded

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *