5. Longest Palindromic Substring

Description

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.

💡 Hint 1:
How can we reuse a previously computed palindrome to compute a larger palindrome?

💡 Hint 2:
If “aba” is a palindrome, is “xabax” a palindrome? Similarly is “xabay” a palindrome?

💡 Hint 3:
Complexity based hint:
If we use brute-force and check whether for every start and end position a substring is a palindrome we have O(n^2) start - end pairs and O(n) palindromic checks. Can we reduce the time for palindromic checks to O(1) by reusing some previous computation.

Submitted Code

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def search(left, right):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left+1:right]

        max_palindrome = s[0]
        for i in range(len(s)):
            candidate = search(i, i)        # 가운데 하나(홀수 길이)
            if len(candidate) > len(max_palindrome):
                max_palindrome = candidate

            candidate = search(i, i+1)      # 가운데 두개(짝수 길이)
            if len(candidate) > len(max_palindrome):
                max_palindrome = candidate
        return max_palindrome

Runtime: 239 ms | Beats 79.53%
Memory: 19.16 MB | Beats 91.88%

가운데를 기준으로 좌우가 같다는 성질을 이용할 수 있다. 모든 문자에 대해 가운데가 하나일 경우와 두 개일 경우 최대로 확장 가능한 길이를 확인해야 한다.

Other Solutions

1st

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""

        def expand_around_center(s: str, left: int, right: int):
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return right - left - 1


        start = 0
        end = 0

        for i in range(len(s)):
            odd = expand_around_center(s, i, i)
            even = expand_around_center(s, i, i + 1)
            max_len = max(odd, even)
            
            if max_len > end - start:               # 중심 i를 기준으로 왼쪽/오른쪽 이동
                start = i - (max_len - 1) // 2
                end = i + max_len // 2
        
        return s[start:end+1]

time complexity: 𝑂(𝑛²)
space complexity: 𝑂(1)