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

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

A **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.

- The idea is to generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.
- 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
- 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. - 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.
- 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;
}
```