Given a string s, return the longest palindromic substring in s.
Examples
Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer.
Input: s = "cbbd" Output: "bb"
Input: s = "a" Output: "a"
Input: s = "ac" Output: "a"
Constraints
1 <= s.length <= 1000 s consist of only digits and English letters.
Java Solution
Dynammic Programming
class Solution {
public String longestPalindrome(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
String ans = "";
for(int g = 0; g < dp.length; g++){
for(int i = 0, j = g; j < dp.length; i++, j++){
if(g == 0)
dp[i][j] = true;
else if(g == 1){
if(s.charAt(i) == s.charAt(j))
dp[i][j] = true;
}else{
if(dp[i+1][j-1] == true && s.charAt(i) == s.charAt(j))
dp[i][j] = true;
}
if(dp[i][j] == true)
ans = s.substring(i, j+1);
}
}
return ans;
}
}
Expand Around Center
class Solution {
public String longestPalindrome(String s) {
if( s == null || s.length() < 1) return "";
int start = 0;
int end = 0;
for(int i = 0; i < s.length(); i++) {
int oddLength = expandAroundCenter(s, i, i);
int evenLength = expandAroundCenter(s, i, i+1);
int maxLength = Math.max(oddLength, evenLength);
if(maxLength > end-start) {
start = i - (maxLength - 1) / 2;
end = i + maxLength / 2;
}
}
return s.substring(start, end+1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while(L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
}