Longest Palindromic Substring

Problem: Given a string, find the length of the longest palindromic substring in it.

Solution: 

Longest Common Substring can be used to solve this problem. The steps are as follows:

1. Reverse the given string and store the reverse in another string say rev[0..n-1]
2. Longest Common Substring of the given string and rev[] will be the longest palindromic substring.

Implementation:

int LongestPalindromSubString(std::string str)

{

std::string rev = str;

std::reverse(rev.begin(), rev.end());

return LongestCommonSubstring(str, rev);

}

Please find the implementation of Longest Common Substring at the following URL:

http://algods-cracker.blogspot.in/2015/04/longest-common-substring.html

Complexity: O(n²)

Space efficient solution:

We can generate all even length and odd length palindromes and keep track of the longest palindrome seen so far.

1. To generate odd length palindrome, we can fix a center and expand in both directions for longer palindromes.
2. To generate even length palindrome, we can fix two center and expand in both directions for longer palindromes.

We will not be needing any extra space using this approach.

Implementation:

int LongestPalindromSubString(std::string str)

{

int maxLen = 1, len = str.size();

int start = 0; //Can be used to print the substring

for(int i = 1; i < len; ++i)

{

int low = i - 1, high = i; //Even palindromes

while(low >= 0 && high < len && str[low] == str[high])

{

if(high - low + 1 > maxLen)

{

start = low;

maxLen = high - low + 1;

}

--low;

++high;

}

low = i - 1, high = i + 1; //Odd palindromes

while(low >= 0 && high < len && str[low] == str[high])

{

if(high - low + 1 > maxLen)

{

start = low;

maxLen = high - low + 1;

}

--low;

++high;

}

}

//print str[start] to str[start + maxLen - 1]

return maxLen;

}

Complexity: O(n²)