{"post":"

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.
\nCase 2: Check each even and odd substring for each character to find the longest palindrome in a string.

# Algorithm

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

Code:

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

Output:

The longest palindrome substring is cdefedc

Time Complexity: O(N^3)

# Optimized Algorithm

Pass the given array to find the longest prefix in the given string.
The function of finding the longest prefix finds each even length palindrome and odd length palindrome by considering each character as centre.
It updates the start and maximum length of the palindrome substring.
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> \nusing namespace std; 
\nvoid LongestPal(char* str)  
\n{  
\n    int maxLength = 1,start = 0,l, h; 
\n    int len = strlen(str); 
\n    for (int i = 1; i < len; ++i)  
\n    {  
\n        l = i - 1;  
\n        h = i;  
\n        while (l >= 0 && h < len && str[l] == str[h])  
\n        {  
\n            if (h - l + 1 > maxLength)  
\n            {  
\n                start = l;  
\n                maxLength = h - l + 1;  
\n            }  
\n            --l;  
\n            ++h;  
\n        }  
\n        l = i - 1;  
\n        h = i + 1;  
\n        while (l >= 0 && h < len && str[l] == str[h])  
\n        {  
\n            if (h - l + 1 > maxLength)  
\n            {  
\n                start = l;  
\n                maxLength = h - l + 1;  
\n            }  
\n            --l;  
\n            ++h;  
\n        }  
\n    }  
\n    if(maxLength==1)
\n    {
\n        cout<<\"No palindrome substring exists\"<<endl;
\n    }
\n    else
\n    {
\n        cout<<\"Longest palindrome substring is: \";
\n        for( int i = start; i < start + maxLength; ++i )  
\n            cout << str[i];  
\n    }
\n}  
\nint main()  
\n{  
\n    LongestPal(\"abcdefedcxyt\");
\n    return 0;
\n}

Output:

Longest palindrome substring is: cdefedc

Time Complexity: O(N^2)

\n","title":"Find the longest palindrome in a string Problem","authorDetails":{"name":"Ankita Khan","slug":"ankita-khan"},"description":"Program to find 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.","slug":"find-the-longest-palindrome-in-a-string-problem/","articleId":"636a83447bb1ce5072622b73","bookmarkStatus":{"isBookmarked":false,"bookmarkId":null}}