Longest Palindromic Substring

Q: 가장 긴 회문 부분 문자열은 가장 긴 회문 부분 수열과 어떻게 다른가요?

부분 문자열은 연속된 문자들의 나열이고, 부분 수열은 문자를 건너뛸 수 있습니다. "character" 에서 가장 긴 회문 부분 문자열은 "ara" 이지만, "carac" 은 길이가 5인 회문 부분 수열입니다. 부분 수열 버전은 양 끝의 문자가 다를 때 한쪽 끝을 제외하는 (i, j) 테이블을 사용해 풉니다.

보통투 포인터 동적 계획법

+10

소문자 영어 문자로 이루어진 문자열 s가 주어집니다. 가장 긴 회문 부분 문자열을 반환하세요. 회문 부분 문자열이란 앞에서 읽어도 뒤에서 읽어도 똑같은 연속된 문자들의 가장 긴 구간입니다. 가장 긴 길이를 공유하는 부분 문자열이 여러 개라면 가장 왼쪽에서 시작하는 부분 문자열을 반환하세요.

함수

longestPalindrome(s: string) → string

sstring: 검색할 소문자 문자열
반환값string: s에서 가장 긴 회문 부분 문자열. 가장 긴 회문 부분 문자열이 여러 개라면 가장 왼쪽에 있는 것

제약 조건

1 ≤ s.length ≤ 2000
s에는 소문자 영어 문자만 들어 있습니다.
가장 긴 길이의 회문이 여러 개이면, 시작 인덱스가 가장 작은 회문이 정답입니다.

예제

입력: s = "bananas"
출력: "anana"
설명: "anana"는 양쪽 끝에서 읽어도 같고 글자가 5개입니다. 더 긴 부분 문자열은 없습니다. "banana"는 b로 시작하고 a로 끝나며, "ananas"는 a로 시작하고 s로 끝납니다. 그리고 전체 단어는 b로 시작하고 s로 끝납니다.

입력: s = "xyzzyabba"
출력: "yzzy"
설명: "yzzy"와 "abba"는 둘 다 길이가 4인 회문이며, 이보다 긴 것은 없습니다. "yzzy"는 인덱스 1에서 시작하고 인덱스 5에서 시작하는 "abba"보다 앞서므로 동률에서 승리합니다.

입력: s = "abcd"
출력: "a"
설명: 같은 문자가 두 개 없으므로 모든 회문은 한 글자입니다. 가장 왼쪽에 있는 문자는 "a"입니다.

제출 시 숨은 테스트 +18개

후속 질문

답을 O(n) 시간 내에 찾을 수 있나요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

회문은 가운데를 기준으로 대칭이며, 그 가운데는 한 글자(홀수 길이, 예: "anana")이거나 같은 두 글자 사이의 간격(짝수 길이, 예: "abba")입니다. 각 부분 문자열을 따로 확인하면 이러한 구조를 무시하게 되고 O(n³)의 비용이 듭니다. 각 회문을 가운데에서 바깥쪽으로 확장하면 모든 비교를 재사용할 수 있으므로, 추가 메모리 O(1)로 탐색 시간을 O(n²)까지 줄일 수 있습니다.

모든 부분 문자열 확인

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

부분 문자열은 첫 번째 인덱스 i와 마지막 인덱스 j로 정해집니다. 두 개의 포인터를 사용해 확인합니다. s[i]와 s[j]를 비교한 다음, s[i+1]과 s[j-1]을 비교하는 식으로 진행하다가 처음으로 일치하지 않는 문자가 나오면 멈춥니다. 일치하지 않는 문자가 나오기 전에 포인터가 만나거나 교차하면 해당 부분 문자열은 회문입니다. 찾은 것 중 가장 긴 회문을 유지합니다.

동일한 길이일 때의 규칙을 적용하려면 시작 인덱스를 왼쪽에서 오른쪽으로 살펴보고, 새 회문이 기존 회문보다 엄격하게 더 긴 경우에만 최선의 결과를 바꿉니다. 따라서 나중에 발견한 길이가 같은 회문은 앞서 발견한 회문을 대체하지 않으며, 가장 왼쪽에 있는 회문을 반환합니다.

이 방법은 n(n+1)/2개의 모든 부분 문자열을 살펴보므로 정답을 놓칠 수 없습니다. 하지만 각 확인 과정에서 부분 문자열 길이의 절반만큼 살펴볼 수 있어 느립니다. a가 2000개 있는 문자열에서는 모든 부분 문자열이 회문이고 각 확인 과정은 중간 지점까지 진행됩니다. 즉, 문자 비교 횟수는 약 n³/12 ≈ 6.7 × 10^8회입니다.

알고리즘

첫 번째 문자를 최선의 결과로 설정합니다. 시작 인덱스는 0, 길이는 1입니다.
각 시작 위치 i와 각 끝 위치 j ≥ i에 대해, 문자가 다르거나 포인터가 만날 때까지 양쪽 끝에서 가운데 방향으로 문자를 비교합니다.
불일치 없이 포인터가 만나면 s[i..j]는 회문입니다.
그 길이 j-i+1가 현재 최선의 길이보다 길면 i와 해당 길이를 기록합니다.
최선의 시작 위치와 최선의 길이에 해당하는 부분 문자열을 반환합니다.

def longestPalindrome(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i, n):
            # Compare s[i..j] from both ends toward the middle
            left, right = i, j
            while left < right and s[left] == s[right]:
                left += 1
                right -= 1
            is_palindrome = left >= right
            if is_palindrome and j - i + 1 > best_len:
                best_start, best_len = i, j - i + 1
    return s[best_start:best_start + best_len]

길이별 회문 표

핵심 아이디어

완전 탐색은 이미 학습한 내용을 잊어버립니다. "anana"를 검사할 때 a와 a를 비교한 다음 n과 n을 비교하는데, 두 번째 비교는 이미 수행한 "nan" 전체 검사와 같습니다. 작업을 줄이는 규칙은 다음과 같습니다. 양 끝이 일치하고 그 사이의 부분 문자열 s[i+1..j-1]이 회문이면 s[i..j]도 회문입니다. 비교 한 번과 저장된 답 하나로 각 부분 문자열을 판별할 수 있습니다.

답을 표 pal[i][j]에 저장하고 길이순으로 채웁니다. 글자 하나는 모두 회문입니다. 글자 두 개로 된 부분 문자열은 두 글자가 일치하면 회문입니다. 더 긴 길이에서는 이 규칙을 사용합니다. 내부 부분 문자열은 길이가 두 글자 짧으므로 해당 칸이 이미 채워져 있습니다.

"bananas"에서 pal[1][5]("anana")는 s[1]과 s[5]가 모두 a이고 pal[2][4]("nan")이 참이므로 참입니다. 길이는 늘어나는 순서로 진행하고 시작 위치는 왼쪽에서 오른쪽으로 이동하므로, 새로 가장 긴 길이를 기록하는 첫 회문은 그 길이에서 가장 왼쪽에 있는 회문이기도 합니다. 약 n²/2개의 칸을 각각 O(1)에 처리하므로 시간 복잡도는 O(n²)입니다. 그 대가로 메모리가 필요하며, n = 2000일 때 4 × 10^6개의 칸을 사용합니다.

알고리즘

모든 값이 false인 n × n 표 pal을 만듭니다.
길이를 1부터 n까지 차례로 확인하고, 끝 위치 j = i+length-1가 문자열 범위 안에 있는 각 시작 위치 i에 대해 양 끝 문자를 확인합니다.
두 문자가 일치하고 길이가 2 이하이거나 pal[i+1][j-1]가 true이면 pal[i][j]를 표시합니다.
표시된 칸의 길이가 지금까지의 최댓값보다 크면 i와 길이를 기록합니다.
가장 좋은 시작 위치에서 부분 문자열을 반환합니다.

def longestPalindrome(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways
    pal = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Equal ends, and the part inside them is a palindrome (or too short to matter)
            if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
                if length > best_len:
                    best_start, best_len = i, length
    return s[best_start:best_start + best_len]

모든 중심을 기준으로 확장

핵심 아이디어

모든 회문에는 중심이 있습니다. "anana"처럼 길이가 홀수인 회문은 문자 하나를 중심으로 하고, "abba"처럼 길이가 짝수인 회문은 가운데 두 문자 사이의 간격을 중심으로 합니다. 길이가 n인 문자열에는 문자 n개와 간격 n-1개가 있으므로 가능한 중심은 2n-1개입니다.

각 중심에서 양쪽으로 한 문자씩 바깥쪽으로 이동하면서 두 문자가 일치하는지 확인합니다. 이동할 때마다 길이가 두 문자 더 긴 회문임을 확인할 수 있습니다. 처음으로 문자가 일치하지 않거나 문자열의 끝에 도달하면 탐색이 끝납니다. 더 긴 회문은 일치하지 않는 쌍을 포함하게 되므로 같은 중심을 공유할 수 없습니다. 따라서 중심마다 바깥쪽으로 한 번 탐색하면 해당 중심을 둘러싼 가장 긴 회문을 찾을 수 있고, 그중 가장 긴 것이 정답입니다.

"bananas"에서 인덱스 3의 문자 a를 중심으로 시작해 봅시다. 인덱스 2와 4의 문자는 모두 n이고, 인덱스 1과 5의 문자는 모두 a입니다. 인덱스 0과 6의 문자는 각각 b와 s이므로 길이 5에서 탐색이 멈춥니다. 시작 위치는 3 - (5-1)/2 = 1이므로 "anana"를 얻습니다. 동일한 공식인 center - (length-1)/2의 내림값은 간격을 중심으로 하는 경우에도 적용됩니다.

중심을 왼쪽에서 오른쪽으로 탐색하고, 길이가 엄격히 더 긴 경우에만 최선의 값을 갱신합니다. 길이가 같은 두 회문은 홀짝성이 같고, 중심이 더 이른 회문이 더 일찍 시작하므로 가장 왼쪽 회문이 선택됩니다. 최악의 경우는 같은 문자가 반복되는 문자열입니다. 각 중심에서 더 가까운 끝까지 탐색하므로 n = 2000일 때 약 n²/2 = 2 × 10^6번의 단계가 필요하고, 메모리는 정수 몇 개면 충분합니다.

알고리즘

expand(left, right)를 작성하세요. 두 인덱스가 모두 문자열 안에 있고 문자가 일치하는 동안 left를 감소시키고 right를 증가시키세요. right-left-1을 반환하세요.
0부터 n-1까지 각 중심에 대해 expand(center, center)와 expand(center, center+1) 중 더 큰 값을 취하세요.
그 길이가 최댓값보다 크면 최댓값의 시작 위치를 내림한 center - (length-1)/2로 설정하고, 최댓값의 길이를 해당 길이로 설정하세요.
최댓값의 시작 위치와 길이에 해당하는 부분 문자열을 반환하세요.

def expand(s, left, right):
    # Grow outward while the two ends match; return the palindrome's length
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


def longestPalindrome(s):
    best_start, best_len = 0, 1
    for center in range(len(s)):
        # Odd lengths grow from one letter, even lengths from the gap after it
        length = max(expand(s, center, center), expand(s, center, center + 1))
        if length > best_len:
            best_start = center - (length - 1) // 2
            best_len = length
    return s[best_start:best_start + best_len]

함정과 경계 사례

아이디어는 간단하지만, 버그는 세부 사항에 숨어 있습니다. 짝수 길이 중심, 탐색 후의 길이, 동률 처리 규칙, 슬라이싱이 그렇습니다.

문자 주변에서만 확장하면 짝수 길이 회문을 모두 놓칩니다. "abba"에서는 "abba"가 아니라 "a"를 반환합니다.
탐색은 양 끝을 각각 한 칸씩 지나서 멈추므로, 회문은 s[left+1..right-1]이고 길이는 right-left-1입니다. right-left+1을 사용하면 일치하지 않는 문자가 두 개 추가됩니다.
길이가 같을 때 최선의 결과를 교체하면 가장 오른쪽 회문이 반환됩니다. 따라서 "xyzzyabba"에서 "yzzy"가 아니라 "abba"가 반환됩니다.
간격 중심의 경우 center - length/2는 왼쪽으로 한 칸 더 이동합니다. "xyzzyabba"에서 인덱스 2 다음의 간격은 길이가 4이며, 시작 위치는 0이 아니라 2 - (4-1)/2 = 1입니다.
슬라이싱 API는 서로 다릅니다. C++의 substr과 C#의 Substring은 길이를 받지만, JavaScript의 substring과 Java의 substring은 끝 인덱스를 받습니다.
표에서 시작 위치가 0인 행부터 채우면, pal[i+1][j-1]이 채워지기 전에 이를 읽게 됩니다. 길이 순서대로 채우거나, 시작 위치를 끝에서부터 순회하세요.

자주 묻는 질문4

가장 긴 회문 부분 문자열의 시간 복잡도는 얼마인가요?

중심을 기준으로 확장하는 방법은 O(n²) 시간이 걸리고 추가 메모리는 O(1)입니다. 테이블을 사용하는 방법도 O(n²) 시간이 걸리지만 O(n²) 메모리가 필요하며, 모든 부분 문자열을 확인하는 방법은 O(n³) 시간이 걸립니다. Manacher 알고리즘은 O(n)을 달성하지만, 면접관이 이를 기대하는 경우는 드뭅니다.

중심을 기준으로 확장할 때 왜 2n-1개의 중심을 사용하나요?

홀수 길이 회문에는 가운데 글자가 있고, 짝수 길이 회문에는 같은 글자 두 개 사이에 가운데 간격이 있습니다. n개의 글자로 이루어진 문자열에는 글자가 n개 있고 이웃한 글자 사이에 간격이 n-1개 있습니다. 글자만을 기준으로 확장하면 "abba"와 같은 회문을 놓치게 됩니다.

Manacher 알고리즘이란 무엇인가요?

모든 중심을 기준으로 가장 긴 회문을 총 O(n) 시간에 찾습니다. 지금까지 가장 오른쪽까지 도달한 회문을 유지하고, 그 안에 있는 중심은 대칭 중심의 답에서 시작하므로 어떤 문자도 처음부터 다시 비교하지 않습니다. 이름을 알아 둘 만한 알고리즘입니다. 면접관들이 보통 원하는 풀이 방식은 중심 확장입니다.

가장 긴 회문 부분 문자열은 가장 긴 회문 부분 수열과 어떻게 다른가요?

부분 문자열은 연속된 문자들의 나열이고, 부분 수열은 문자를 건너뛸 수 있습니다. "character"에서 가장 긴 회문 부분 문자열은 "ara"이지만, "carac"은 길이가 5인 회문 부분 수열입니다. 부분 수열 버전은 양 끝의 문자가 다를 때 한쪽 끝을 제외하는 (i, j) 테이블을 사용해 풉니다.

Python

def longestPalindrome(s):
    # 여기에 코드를 작성하세요

테스트 케이스

케이스 1

케이스 2

케이스 3

입력

s = "bananas"

기대값

"anana"

Longest Palindromic Substring

함수

제약 조건

예제

힌트

풀이

모든 부분 문자열 확인

길이별 회문 표

모든 중심을 기준으로 확장

함정과 경계 사례

자주 묻는 질문4

비슷한 문제