Find the longest palindrome in a string Problem

Input: abcdefedcxyt

Output: cdefedc

Explanation: The input contains a string. The output is the longest palindrome which is present in the given string. One just has to check on the substrings to check for the palindrome of each. There are two approaches to solve it:

Case 1: Check each substring is palindrome or not.
Case 2: Check each even and odd substring for each character to find the longest palindrome in a string.

# Algorithm

1. Pass the given array and its length to find the longest prefix in the given string.
2. The function of finding the longest prefix, in turn, calls the function prefix to compare each word letter by letter for the prefix.
3. Return the prefix which is the longest and is common among all the strings.
4. If palindrome substring exists print it or else print an appropriate error message.

Code:

#include<iostream>
#include<string>
using namespace std;
bool isPalindrome(string str)
{
    if (str.length() == 0)
        return false;
    if (str.length() == 1)
        return true;
    int halflen = str.length() / 2;
    int len = str.length() - 1;
    for (int i = 0; i < halflen; i++)
    {
        if (str[i] != str[len])
        {
            return false;
        }
        len--;
    }
    return true;
}
string LongestPal(string istr)
{
    int palindromeLength = 0;
    string rstring = "";
    for (int i = 0; i < istr.length(); ++i)
    {
        string subString = "";
        subString += istr[i];
        for (int j = i + 1 ; j < istr.length(); j++)
        {
            subString += istr[j];
            if( isPalindrome (subString) ) 
            {
                if (palindromeLength < subString.length())
                {
                    palindromeLength = subString.length();
                    rstring += subString;
                }
            }
        }
    }
    return rstring;
}
int main()
{
    string res = LongestPal("abcdefedcxyt");
    if (res=="")
        cout<<"No palindrome substring exists"<<endl;
    else    
        cout<<"The longest palindrome substring is " << res <<endl;
    return 0;
}

Output:

The longest palindrome substring is cdefedc

Time Complexity: O(N^3)

 

# Optimized Algorithm

1. Pass the given array to find the longest prefix in the given string.
2. The function of finding the longest prefix finds each even length palindrome and odd length palindrome by considering each character as centre.
3. It updates the start and maximum length of the palindrome substring.
4. If palindrome substring exists print it or else print an appropriate error message depending on the value of the maximum length of the palindrome substring.

Optimized Code:

#include <bits/stdc++.h> 
using namespace std; 
void LongestPal(char* str)  
{  
    int maxLength = 1,start = 0,l, h; 
    int len = strlen(str); 
    for (int i = 1; i < len; ++i)  
    {  
        l = i - 1;  
        h = i;  
        while (l >= 0 && h < len && str[l] == str[h])  
        {  
            if (h - l + 1 > maxLength)  
            {  
                start = l;  
                maxLength = h - l + 1;  
            }  
            --l;  
            ++h;  
        }  
        l = i - 1;  
        h = i + 1;  
        while (l >= 0 && h < len && str[l] == str[h])  
        {  
            if (h - l + 1 > maxLength)  
            {  
                start = l;  
                maxLength = h - l + 1;  
            }  
            --l;  
            ++h;  
        }  
    }  
    if(maxLength==1)
    {
        cout<<"No palindrome substring exists"<<endl;
    }
    else
    {
        cout<<"Longest palindrome substring is: ";
        for( int i = start; i < start + maxLength; ++i )  
            cout << str[i];  
    }
}  
int main()  
{  
    LongestPal("abcdefedcxyt");
    return 0;
}

Output:

Longest palindrome substring is: cdefedc

Time Complexity: O(N^2)