문제

문자열 s가 주어질 때, s안에서 가장 긴 팰린드롬 부분 문자열을 반환하여라.

Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

풀이

꽤 애먹었던 문제다. 일단 Palindrome은 짝수 길이의 palindrome와 홀수 길이의 palindrome이 존재한다. 언뜻 보면 두 종류의 palindrome을 구하는 함수를 따로 구현해야 할 것 같지만, 초기 왼쪽과 오른쪽을 가리키는 포인터의 간격을 조정함으로써 하나의 함수로 구할 수 있다.

1) Two-Pointer방식을 이용한 find_palindrome함수 구현
구현은 생각보다 간편하다. 왼쪽과 오른쪽을 가리키는 포인터가 문자열의 범위를 넘지 않으면서, 서로 가리키는 문자가 같은 동안에 계속 왼쪽과 오늘쪽을 가리키는 포인터의 값을 조정하는 함수를 구현하면 된다.

2) 예외처리
find_palindrome함수는 길이가 2 이상인 문자열에서 동작한다. 또한, 파이썬은 문자열 반전에 매우 빠른 성능을 보여 주므로, 이 두 사항을 예외로 처리하기로 한다.

3) Sliding-Window기법을 이용하여 최대값 구하기.
이제 문자열의 문자들을 순회하며, find_palindrome이 반환하는 palindrome중 문자열의 길이가 가장 긴 문자열을 찾는다.

이를 Python으로 구현하면 다음과 같다.

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

        # 팰린드롬을 찾는 함수 구현
        def find_palindrome(left: int, right: int) -> str:
            while left > -1 and right < len(s) and s[left] == s[right]:
                left -= 1; right += 1

            return s[left + 1: right]

        # 예외 처리
        if len(s) < 2 or s == s[::-1]:
            return s

        answer = ''
        
        # 슬라이딩 윈도우의 크기 비교
        for idx in range(len(s) - 1):
            answer = max(answer, find_palindrome(idx, idx + 1), find_palindrome(idx, idx + 2), key=len)

        return answer