Please see the solution of LC 647. Palindromic Substrings before proceeding as it is the exact same concept.
Approach 1: Recursion
The idea is to imagine each index as the center of the palindrome and try extending to the left and right. We have to check for both odd length palindromes and even length palindromes. For the even length case, we consider index i and i+1 to be the center of the string. If s[i]==s[i+1] then we move on to check s[i-1] and s[i+2] and so on. The odd length case is intuitive.
See this solution by keshavk for pictorial representation.
public class Solution {
private int lo, maxLen;
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2)
return s;
for (int i = 0; i < len-1; i++) {
extendPalindrome(s, i, i); //assume odd length, try to extend Palindrome as possible
extendPalindrome(s, i, i+1); //assume even length.
}
return s.substring(lo, lo + maxLen);
}
private void extendPalindrome(String s, int j, int k) {
while (j >= 0 && k < s.length() && s.charAt(j) == s.charAt(k)) {
j--;
k++;
}
if (maxLen < k - j - 1) {
lo = j + 1;
maxLen = k - j - 1;
}
}}
Time complexity: O(n^2)
Approach 2: Dynamic Programming
Let us define a 2D dp array where dp[i][j] represents whether substring from index i to j is a palindrome. Clearly, for all i==j, the string will be a palindrome as it contains only one character. Further, for all i>j, it is an invalid substring as we are assuming that i comes before j. Now, for a substring i..j to be a palindrome, it is mandatory for i+1..j-1 to be a palindrome. Further, s[i] should be equal to s[j]. Hence, dp[i][j] = dp[i+1][j-1] && s[i]==s[j].
See solution of LC 647. Palindromic Substrings for more details.
string longestPalindrome(string s) {
int len = s.length(), maxLen = 1, start=0;
if (!len)
return "";
bool dp[len][len];
for (int i=0; i<len; i++)
for (int j=0; j<len; j++)
if (i>=j)
dp[i][j] = 1;
else
dp[i][j] = 0;
int j=1;
while (j<len) {
for (int i=0; i<j; i++) {
dp[i][j] = dp[i+1][j-1] && s[i] == s[j];
if (dp[i][j] && j-i+1>maxLen) {
maxLen = j-i+1;
start = i;
}
}
j++;
}
return s.substr(start, maxLen);
}
Time complexity: O(n^2)