Given a string "s" of length "n", the task is to find the length of the longest palindromic substring in it.
A substring is a contiguous sequence of characters within a string.
A palindrome is a sequence of characters which reads the same backward as forward, such as "madam" or "racecar".
Input: "aaaabbaa", Output: 6
Input: "abcbab", Output: 5
Note: The idea of reversing string "s1" to find "s2" and then finding the longest common substring between s1 and s2 is flawed and fails when there is a reversed copy of a non-palindromic substring in some other part of the string. i.e., "qv" and "vq" in "otafsngqvoijxuvqbztv".
This approach returns a wrong result in the original form, therefore it is not included in the solutions given below.
Solutions
Method 1: DP (Bottom Up)
One naive approach to solving the problem is to generate all possible substrings of the given string and print the length of the longest substring, which is also a palindrome. But this solution takes O(n^3) time, where n is the length of the given string.
This O(n^3) solution can be optimized by storing results of Overlapping Subproblems (Dynamic Programming).
In this solution, we need to maintain a boolean table[n][n] that is filled in a bottom-up manner.
The value of table[i][j] is "true" if the substring from "i th" to "j th" index is a palindrome, otherwise false.
We know that a single-character string is always a palindrome of length one, i.e., t[i][j] = true, where i=0, j=0.
We also know that a two-character string is a palindrome if both characters are equal, i.e. t[i] [j] = true, where i = 0 and j = 1.
Now the only task left is to check for sub-strings of length 3 or more.
A string with 3 or more characters is a palindrome if the corner characters of the string are equal and the middle sub-string is also a palindrome, i.e. s.charAt(i) == s.charAt(j) && t[i+1][j-1] == true.
Complexity
The time complexity of this solution is O(n^2).
In addition, O(n^2) auxiliary space was used by the table.