3844. Longest Almost-Palindromic Substring

2026-03-02
leetcode
리트코드 3844번 풀이

문제

Longest Almost-Palindromic Substring

풀이

아이디어

AI도 삽질하게 만드는 문제,, 문제 자체는 다른 팰린드롬 문제와 비슷하게 느껴졌는데 왜 이렇게 어렵게 풀었을까요?? (의문)

중간에서부터 양쪽으로 확장해 나가는 투포인터 문제이다. 핵심 컨셉은 5번 Longest Palindromic Substring 문제와 완전히 똑같다. 이 문제의 특징은 중간에 mismatch를 딱 한번 허용한다는건데, 그래서 내부에서 3가지 경우를 모두 시도해보는 방식으로 풀이했다.

  1. 완벽한 팰린드롬 찾기 → 동시에 불일치 지점 반환받기
  2. 왼쪽 제거 시도 → 완벽한 팰린드롬 찾기
  3. 오른쪽 제거 시도 → 완벽한 팰린드롬 찾기

아마도 이전에 팰린드롬 문제를 풀 때 중심 결정이 번거로워서 expand(mid, mid)와 expand(mid, mid + 1)를 두번 호출하는 방식으로 풀이했었는데, 그것때문에 이 문제 푸는데 오래 걸리지 않았나 싶다. 참고한 풀이에서처럼 idx를 2n개로 잡고, expand(Math.floor(idx / 2), Math.floor((idx + 1) / 2))로 한 번에 처리하는 방식이 훨씬 깔끔한 것 같다.

코드

function almostPalindromic(s: string): number {
  const len = s.length;
  let answer = 0;

  function expand(left: number, right: number) {
    while (left >= 0 && right < len && s[left] === s[right]) {
      left--;
      right++;
    }

    answer = Math.max(answer, right - left - 1);
    return [left, right];
  }

  for (let idx = 0; idx < 2 * len; idx++) {
    // 1. 완벽한 팰린드롬 찾기 → [left, right]은 불일치 지점
    const [left, right] = expand(Math.floor(idx / 2), Math.floor((idx + 1) / 2));
    // 2. 왼쪽 제거 시도
    expand(left - 1, right);
    // 3. 오른쪽 제거 시도
    expand(left, right + 1);
  }

  // 범위가 넘어갔을 수 있기 때문에 최대 길이인 len으로 클리핑해준다.
  return Math.min(answer, len);
}

시간 / 공간 복잡도

  • 시간 복잡도: O(n²) — 2n개 중심마다 최대 O(n) expand
  • 공간 복잡도: O(1)