Given a string s, return the longest palindromic substring in s.
Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.
Example 2:
Input: s = "cbbd"
Output: "bb"
Constraints:
1 <= s.length <= 1000
s consist of only digits and English letters.
longest palindromic substring java
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length() < 1) return "";
int start = 0, end = 0;
for(int i = 0; i < s.length(); i++) {
int len1 = expandAroundCenter(s, i, i);
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if(len > end - start) {
start = i -(len -1) / 2;
end = i + len / 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;
}
}
longest palindromic substring python leetcode
def longestPalindrome(self, s: str) -> str:
longest = '' if not s else s[0]
max_len = 1
size = len(s)
dp=[[False]*size for _ in range(size)]
for start in range(size-1,-1,-1):
dp[start][start]=True
for end in range(start+1,size):
if s[start]==s[end]:
if end - start == 1 or dp[start+1][end-1]:
dp[start][end] = True
if max_len < end - start + 1:
max_len = end - start + 1
longest = s[start: end+ 1]
return longest
