LeetCode 647 - Palindromic Substrings

문자열 안에 존재하는 모든 팰린드롬(회문) 부분 문자열(Substring)의 개수를 세는 Medium 문제다. 모든 부분 문자열을 잘라 검사하는 대신, 각 인덱스와 인덱스 사이를 중심으로 잡고 양옆으로 확장해 나가는 중심 확장법(Expand Around Center)을 적용하여 시간과 공간 효율을 극대화했다.

문제 링크 & 설명

문제 링크: 647. Palindromic Substrings
요약: 문자열 s가 주어졌을 때, s의 부분 문자열 중 팰린드롬인 것의 총 개수를 반환한다. 같은 문자열이라도 시작 또는 끝 위치가 다르면 서로 다른 부분 문자열로 카운트한다.

모든 부분 문자열을 잘라내어 팰린드롬을 검사하면 O(N³)의 시간 복잡도와 불필요한 문자열 객체 생성이 발생한다. 반면 한 중심점에서 시작해 양 끝 문자가 같을 때까지만 포인터를 넓혀가면 이미 검증된 팰린드롬의 양쪽에 문자를 하나씩 덧붙이는 형태가 되어 훨씬 직관적이고 빠르다.

접근 방법

팰린드롬은 중심이 되는 위치에 따라 두 가지 형태로 나뉜다.

홀수 길이 팰린드롬: 단일 문자 중심 (left = i, right = i)
짝수 길이 팰린드롬: 두 문자 사이 중심 (left = i, right = i + 1)

def expand_around_center(self, s: str, left: int, right: int) -> int:
    sub_count = 0

    while left >= 0 and right < len(s) and s[left] == s[right]:
        sub_count += 1
        left -= 1
        right += 1

    return sub_count

expand_around_center 메서드는 주어진 left, right에서 시작하여 양쪽 경계 내에 있고 s[left] == s[right]인 동안 카운트를 1씩 늘리며 left -= 1, right += 1로 확장한다.
메인 루프에서는 0부터 len(s) - 1까지의 모든 인덱스 i에 대해 홀수 중심과 짝수 중심 확장을 각각 호출하여 결과를 누적한다.

복잡도 분석

시간 복잡도: O(n²)
- 가능한 중심점의 개수는 총 2n - 1개이며, 각 중심점에서 최대로 확장할 수 있는 길이는 O(n)이다.
공간 복잡도: O(1)
- 별도의 문자열 슬라이싱이나 DP 테이블 없이 포인터와 카운터 변수만 사용하므로 추가 메모리가 전혀 들지 않는다.

구현 코드

class Solution:

    def expand_around_center(self, s: str, left: int, right: int) -> int:
        sub_count = 0

        while left >= 0 and right < len(s) and s[left] == s[right]:
            sub_count += 1
            left -= 1
            right += 1

        return sub_count

    def countSubstrings(self, s: str) -> int:
        count = 0

        for i in range(len(s)):
            count += self.expand_around_center(s, i, i)
            count += self.expand_around_center(s, i, i + 1)

        return count

요약 및 회고

팰린드롬 검사는 밖에서 안으로 좁히며 검사할 수도 있지만, 안에서 밖으로 확장할 때 훨씬 강력해진다. 확장 과정에서 불일치가 발생하는 즉시 해당 중심점의 탐색을 중단할 수 있기 때문이다. 홀수 중심과 짝수 중심을 별도의 메서드로 깔끔하게 분리해둔 덕분에 코드의 의도가 명확해지고 중복도 줄일 수 있었다.