LeetCode #5 Longest Palindromic Substring: ขยายจากกลาง, DP หรือ Manacher

Longest Palindromic Substring ให้คืน substring สมมาตรที่ยาวที่สุด จุดที่พลาดบ่อยคือ palindrome มีศูนย์กลางได้ทั้งบนตัวอักษรหนึ่งตัวและช่องว่างระหว่างสองตัวครับ

วิธี 1: Expand Around Center (default)

ลองศูนย์กลาง 2n-1 แบบ แล้วขยายซ้าย-ขวาตราบที่ตัวอักษรเท่ากัน เวลาแย่สุด O(n²) แต่ใช้พื้นที่เพิ่ม O(1) โค้ดสั้นและเหมาะกับ constraint ทั่วไป

วิธี 2: Dynamic Programming

ให้ dp[left][right] บอกว่าช่วงนั้นเป็น palindrome เมื่อปลายเท่ากันและช่วงข้างในเป็น palindrome ใช้เวลา O(n²) และพื้นที่ O(n²) เหมาะเมื่อโจทย์ต่อยอดถามหลายช่วง

วิธี 3: Manacher

แปลง odd/even centers ให้อยู่ใน representation เดียว แล้ว reuse รัศมีจาก palindrome ที่ครอบอยู่ ได้เวลา O(n) และพื้นที่ O(n) แต่ invariant ซับซ้อนกว่า ควรใช้เมื่อ input ใหญ่มากหรือ latency บังคับ

from __future__ import annotations

import unittest


def expand_center(s: str) -> str:
    best_left = best_right = 0
    for center in range(2 * len(s) - 1):
        left = center // 2
        right = left + center % 2
        while left >= 0 and right < len(s) and s[left] == s[right]:
            if right - left > best_right - best_left:
                best_left, best_right = left, right
            left -= 1
            right += 1
    return s[best_left:best_right + 1] if s else ""


def dynamic_programming(s: str) -> str:
    n = len(s)
    if n < 2:
        return s
    dp = [[False] * n for _ in range(n)]
    best_left = 0
    best_len = 1
    for right in range(n):
        for left in range(right + 1):
            dp[left][right] = s[left] == s[right] and (
                right - left <= 2 or dp[left + 1][right - 1]
            )
            if dp[left][right] and right - left + 1 > best_len:
                best_left, best_len = left, right - left + 1
    return s[best_left:best_left + best_len]


def manacher(s: str) -> str:
    transformed = "^#" + "#".join(s) + "#$"
    radius = [0] * len(transformed)
    center = right = best_center = best_radius = 0
    for index in range(1, len(transformed) - 1):
        mirror = 2 * center - index
        if index < right:
            radius[index] = min(right - index, radius[mirror])
        while transformed[index + radius[index] + 1] == transformed[index - radius[index] - 1]:
            radius[index] += 1
        if index + radius[index] > right:
            center, right = index, index + radius[index]
        if radius[index] > best_radius:
            best_center, best_radius = index, radius[index]
    start = (best_center - best_radius) // 2
    return s[start:start + best_radius]


class PalindromeTests(unittest.TestCase):
    def test_all_methods(self):
        cases = [("", 0), ("a", 1), ("babad", 3), ("cbbd", 2), ("aaaa", 4)]
        for solve in (expand_center, dynamic_programming, manacher):
            for raw, expected_length in cases:
                result = solve(raw)
                self.assertEqual(len(result), expected_length)
                self.assertEqual(result, result[::-1])
                self.assertIn(result, raw)


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	Expand center	DP	Manacher
เวลา	O(n²)	O(n²)	O(n)
พื้นที่เพิ่ม	O(1)	O(n²)	O(n)
รองรับ odd/even	ใช่	ใช่	ใช่ ผ่าน transform
คืน substring	ตรงไปตรงมา	ตรงไปตรงมา	ต้องแปลง index กลับ
ความเสี่ยง bug	ต่ำ	กลาง	สูง
เหมาะเป็น default	ดีที่สุด	เมื่อ reuse table	เมื่อ n ใหญ่มาก

Recap

• เทสต์ทั้งศูนย์กลางบนตัวอักษรและระหว่างตัวอักษร
• อย่าคืน subsequence แทน substring
• ใช้ expand-around-center เป็น default ที่อ่านง่าย
• เลือก Manacher ต่อเมื่อ constraint คุ้มกับความซับซ้อน