• ㊗️
• 大家
• offer
• 多多！

## Problem

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.


Example 2:

Input: "cbbd"
Output: "bb"


Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

## Code

647. Palindromic Substrings

class Solution {
int maxLen = 0;
int start = 0;

public String longestPalindrome(String s) {
for(int i = 0; i < s.length(); i++){
helper(i, i, s);
helper(i, i + 1, s);
}

return s.substring(start, start + maxLen);
}

private void helper(int left, int right, String s){
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
if(right - left + 1 > maxLen){
start = left;
maxLen = right - left + 1;
}
left--;
right++;
}
}
}

class Solution:
max_len = 0
start = -1
def longestPalindrome(self, s: str) -> str:
for i in range(len(s)):
self.helper(s, i, i)
self.helper(s, i, i + 1)
return s[self.start:self.start + self.max_len]
def helper(self, s: str, start: int, end: int):
while start >= 0 and end < len(s) and s[start] == s[end]:
if end - start + 1 > self.max_len:
self.max_len = end - start + 1
self.start = start
start -= 1
end += 1