• 문제 분류
  1. 질의 많음/구간 → dp[l][r] 전처리 후 O(1)로 답
  2. 최장 부분문자열 → Manacher O(N)
  3. 1회성 확인 → 투포인터/중심확장
  4. 구간 많고 N이 큼 → 정/역 해시로 O(1) 판별
  5. 부분수열 → LPS DP

🔖 알고리즘 구현 방식

1. 중심 확장 - 기본

• 언제 팰린드롬인지 확인 / 최장 팰린드롬인데 N이 크지 않거나 1회성
• 모든 중심(홀수 중심, i, 짝수 중심, i, i + 1)에서 좌우로 확장
  • 홀수 : l = i, r = i
  • 짝수 : l = i, r = i + 1
• 시간복잡도: O(N²)

1. 구간 DP - 구간 질의/전처리

• 구간 [S, E] 질의가 많을 때
  • 숫자 쌍이 작고, 질의가 많은 구조면 거의 이 방식
• 점화식 :
  • dp[i][i] = true
  • dp[i][i + 1] = (a[i] == a[i + 1]
  • dp[l][r] = (a[l] == a[r]) && dp[l + 1][r - 1]
• 외부 반복문 : i → n ~ 1, i-—
• 내부 반복문 : j → i ~ n, j++
• 시간복잡도: O(N²)

1. Manacher - 최장 팰린드롬

• 가장 긴 팰린드롬 부분문자열 길이/위치 문제에서 N이 클 때
• 각 중심의 반지름을 재사용해서 전체를 선형으로 계산
• 시간복잡도: O(N)