Mahdi Shamlou | LeetCode #5 풀이: Longest Palindromic Substring — 내 Expand-Around-Center 모험

Source: Dev.to

여러분 안녕하세요! 마흐디 샴루입니다 — LeetCode 고전 문제 시리즈를 계속 진행합니다 🚀

#4 두 정렬된 배열의 중앙값 이후, 오늘은 문제 #5 — 가장 긴 팰린드롬 부분 문자열에 대해 살펴보겠습니다. 인터뷰에서 자주 등장하는 아주 유명한 문제입니다!

문제 설명

문자열 s가 주어지면, s 안에서 가장 긴 팰린드롬 부분 문자열을 반환하세요.
팰린드롬은 앞뒤가 동일하게 읽히는 문자열을 말합니다.

예시

Input: s = "babad"
Output: "bab"
Explanation: "aba"도 유효한 답변이며 (두 문자열 모두 길이 3)

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

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

풀이: 중심 확장법 (Expand‑Around‑Center)

처음에 모든 가능한 부분 문자열을 검사하는 방법을 생각했는데, 이는 (O(n³) 악몽 😅)이라 너무 비효율적이었습니다. 그때 깨달은 것이 바로: 팰린드롬은 중심에서 양쪽으로 확장될 수 있다는 점입니다!

아이디어는 다음과 같습니다.

• 홀수 길이 팰린드롬의 경우 각 문자 자체를,
• 짝수 길이 팰린드롬의 경우 각 문자 사이의 틈을

가능한 중심으로 간주하고, 양쪽 문자가 일치하는 동안 계속 확장합니다.

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

        start = 0
        end = 0

        def expand_around_center(left: int, right: int):
            while left >= 0 and right  end - start:
                start, end = l1, r1

            if r2 - l2 > end - start:
                start, end = l2, r2

            # Debug prints (optional)
            # print(f"start : {start} and end : {end}")
            # print("#" * 100)

        return s[start:end + 1]

복잡도 분석

• 시간 복잡도: O(n²) – 각 확장은 최악 O(n)까지 진행될 수 있고, 중심은 약 2n개가 존재합니다.
• 공간 복잡도: O(1) – 몇 개의 정수 변수만 사용합니다.

참고 자료

• 이전 글: Mahdi Shamlou | Solving LeetCode #4: Median of Two Sorted Arrays
• 전체 솔루션 저장소: GitHub – mahdi0shamlou/LeetCode