[코테] 리트코드 문자열 조작 5. Longest Palindromic Substring 문제

5. Longest Palindromic Substring

문제 링크

https://leetcode.com/problems/longest-palindromic-substring/description/

문제 설명

Given a string s, return the longest palindromic substring in s.

제한사항

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

입출력 예 #1

1. Input: s = “babad”
2. Output: “bab”
3. Explanation: “aba” is also a valid answer.

입출력 예 #2

1. Input: s = “cbbd”
2. Output: “bb”

문제 풀이

투포인터 기법으로 짝수, 홀수 슬라이딩을 사용하여 가장 큰 펠린드롬 문자열을 출력한다.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 펠린드롬 판별 및 투 포인터 확장
        def expand(left: int, right: int) -> str:
            while left >= 0 and right <= len(s) and s[left] == s[right-1] :
                left -= 1
                right += 1
            return s[left + 1:right -1]

        # 해당 사항이 없을 때 빠르게 리턴
        if len(s) < 2 or s == s[::-1]:
            return s 
        
        result = ''
        # 슬라이딩 윈도우 우측으로 이동
        for i in range(len(s) - 1) :
            result = max(result, 
            expand(i, i + 1),
            expand(i, i + 2), 
            key=len)

        return result