# a function to find out longest palindrome in a given string

posted Jun 22 2 min read

# A function to find out the longest palindrome in a given string

Example for finding the longest palindrome with proper explanation below given example:

palindrome is a word, phrase, or sentence that reads the same backward or forward--such as Madam, I'm Adam. Semordnilaps (the word palindromes in reverse) are words that spell other words when spelled backward (for example, star/rats, drawer/reward).

We can find the longest palindrome substring in (n^2) time with O(1) extra space.

1. The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
2. To generate odd length palindrome, Fix a center and expand in both directions for longer palindromes, i.e. fix i (index) as a center and two indices as i1 = i+1 and i2 = i-1
3. Compare i1 and i2 if equal then decrease i2 and increase i1 and find the maximum length.
Use a similar technique to find the even-length palindrome.
4. Take two indices i1 = i and i2 = i-1 and compare characters at i1 and i2 and find the maximum length till all pair of compared characters are equal and store the maximum length.
5. Print the maximum length.

The function is a logic by which we can implement this logic on any given string to find out the longest palindrome

``````
// A O(n^2) time and O(1) space program to
// find the longest palindromic substring
#include <bits/stdc++.h>
using namespace std;

// A utility function to print
// a substring str[low..high]
void printSubStr(char* str, int low, int high)
{
for (int i = low; i <= high; ++i)
cout << str[i];
}

// This function prints the
// longest palindrome substring (LPS)
// of str[]. It also returns the
// length of the longest palindrome
int longestPalSubstr(char* str)
{
// The result (length of LPS)
int maxLength = 1;

int start = 0;
int len = strlen(str);

int low, high;

// One by one consider every
// character as center point of
// even and length palindromes
for (int i = 1; i < len; ++i) {
// Find the longest even length palindrome
// with center points as i-1 and i.
low = i - 1;
high = i;
while (low >= 0 && high < len
&& str[low] == str[high]) {
if (high - low + 1 > maxLength) {
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}

// Find the longest odd length
// palindrome with center point as i
low = i - 1;
high = i + 1;
while (low >= 0 && high < len
&& str[low] == str[high]) {
if (high - low + 1 > maxLength) {
start = low;
maxLength = high - low + 1;
}
--low;
++high;
}
}

cout << "Longest palindrome substring is: ";
printSubStr(str, start, start + maxLength - 1);

return maxLength;
}

// Driver program to test above functions
int main()
{
char str[] = "vanillaicecreamisfun";
cout << "\nLength is: "
<< longestPalSubstr(str)
<< endl;
return 0;
}

``````