Problem

Solution

1) 투 포인터가 중앙을 중심으로 확장하는 풀이

우선 두 개의 포인터를 사용한다. 2칸 짜리 윈도우를 가지는 포인터와 3칸 짜리 윈도우를 가지는 포인터를 구성한다. 팰린드롬은 "bb"처럼 짝수 일 때도 있고, "bab"처럼 홀수 일 때도 있기 때문. 따라서 짝수, 홀수 모든 경우에 대해 판별한다.
2개의 윈도우 포인터는 왼쪽부터 오른쪽으로 이동하는 슬라이딩 윈도우이다. (오른쪽으로 이동한다는 뜻)

class Solution:
    def longestPalindrome(self, s: str) -> str:
    	# 입력 문자가 1글자이거나 입력 문자를 뒤집었을 때 입력 문자와 동일한 경우 입력 문자를 리턴
        if len(s) < 2 or s == s[::-1]: 
            return s
        
        def expand(left:int, right:int):
        	# 윈도우가 길이 내에 있고, 윈도우 양끝의 문자가 같으면 윈도우 크기 확장
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            return s[left + 1: right] # 해당 윈도우의 문자열 리턴
        
        result = ''
        # 문자별 해당 문자를 기준으로 윈도우 크기를 변경하며 가장 긴 팰린드롬을 찾기위해 반복
        for i in range(0, len(s) - 1):
        	# 가장 긴 공통 문자를 담고 있는 result, 현재 문자를 기준으로 한 가장 긴 공통 문자(홀수), 현재 문자를 기준으로 한 가장 긴 공통길이(짝수)를 비교하여 가장 긴 공통 문자를 찾는다.
            result = max(result,
                        expand(i, i + 1), # 크기가 늘어나는 짝수 윈도우 포인터
                        expand(i, i + 2), # 크기가 늘어나는 홀수 윈도우 포인터
                        key=len)
            
        return result