문제 설명

문자열 s가 주어졌을 때, s의 substring 중 길이가 가장 긴 palindrome substring을 반환해야 하는 문제이다.
Palindrome: 거꾸로 뒤집어도 똑같은 문자열

문제 출처: https://leetcode.com/problems/longest-palindromic-substring/

문제 풀이

Brute Force로 접근한다면, 이중반복문$(O(n^2))$을 순회하며 substring의 시작과 끝 지점을 돌며 해당 substring이 palindrome인지 확인$(O(n))$해야 한다. 그래서 총 $O(n^3)$의 시간이 소요된다. 이는 매우 비효율적이므로 더 효율적인 풀이를 생각해야 한다.
다른 방법으로 길이가 짧은 substring이 palindrome인지 확인한 후, palindrome이라면 substring을 좌우로 한 칸씩 늘린 substiring이 palindrome인지 확인하면 확인 시간이 $O(1)$로 줄어든다. 중간 문자열이 이미 palindrome인지 알기 때문에, 끝 문자열들만 비교하면 되기 때문이다.

def checkPalindrome(
    s, l, r, 
    palindrome_substring, 
    palindrome_length
):
    while l >= 0 and r < len(s) and s[l] == s[r]:
        if palindrome_length < (r - l + 1):
            palindrome_substring = s[l : r + 1]
            palindrome_length = r - l + 1
        l -= 1
        r += 1

    return palindrome_substring, palindrome_length

class Solution:
    def longestPalindrome(self, s: str) -> str:

        palindrome_length = 0
        palindrome_substring = ''

        for i in range(len(s)):
            # check odd palindrome
            palindrome_substring, palindrome_length = checkPalindrome(
                s, i, i, 
                palindrome_substring, 
                palindrome_length
            )

            # check even palindrome
            palindrome_substring, palindrome_length = checkPalindrome(
                s, i, i + 1, 
                palindrome_substring, 
                palindrome_length
            )

        return palindrome_substring