**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:

- Reverse the given string and store the reverse in another string say rev[0..n-1]
- 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:

**Complexity:**O(n

^{2})

**Space efficient solution:**

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

- To generate odd length palindrome, we can fix a center and expand in both directions for longer palindromes.
- 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

^{2})

## No comments:

## Post a Comment