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:
    def longestPalindrome(self, s: str) -> str:
        res = ''

        for i in range(len(s)):
            for j in range(len(s), i, -1):
                if len(res) >= (j - i):
                    break
                if s[i:j] == s[i:j][::-1]:
                    res = s[i:j]
                    break

        return res