5. Longest Palindromic Substring

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• 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