← 23주차 · 트리 DP와 문자열 매칭
어려움문자열

가장 긴 팰린드롬 부분 문자열

문자열 s가 주어져요. s의 연속된 부분 문자열 중 팰린드롬(앞에서 읽으나 뒤에서 읽으나 같은 문자열)인 가장 긴 것의 길이를 반환해요.

각 자리를 중심으로 잡고 좌우로 같은 글자인 동안 넓혀 가면 그 중심에서의 가장 긴 팰린드롬을 알 수 있어요. 팰린드롬은 길이가 홀수일 수도(중심이 글자 하나) 짝수일 수도(중심이 두 글자 사이) 있으니 두 경우를 모두 봐요.

이 중심 확장은 O(n²)이에요. 대칭성을 재사용하는 매내처 알고리즘을 쓰면 O(n)까지 줄일 수 있어요.

예시

예시 1
입력
s = "babad"
출력
3
설명
"bab" 또는 "aba"가 길이 3으로 가장 길어요.
예시 2
입력
s = "cbbd"
출력
2
설명
"bb"가 길이 2예요.
예시 3
입력
s = "abc"
출력
1
설명
팰린드롬이 한 글자짜리뿐이에요.

제한 사항

  • 0 ≤ s.length ≤ 1,000
  • s는 소문자 알파벳으로 이루어져요.
각 인덱스를 중심으로 좌우로 넓히는 expand(l, r)을 만들어 팰린드롬 길이 r - l - 1을 돌려주게 해요. 모든 위치에서 홀수 중심(i, i)과 짝수 중심(i, i + 1) 두 경우의 길이를 구해 최댓값을 기록해요.
javascript
function longestPalindrome(s) {
  if (s.length === 0) return 0;
  let best = 1;
  function expand(l, r) {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--;
      r++;
    }
    return r - l - 1;
  }
  for (let i = 0; i < s.length; i++) {
    best = Math.max(best, expand(i, i), expand(i, i + 1));
  }
  return best;
}
이전 문제부분 문자열 찾기 (KMP)
다음 문제문자열 파싱 + 정렬
에디터를 불러오고 있어요…
코드를 작성하고를 눌러 예시 테스트를 확인해 보세요.