Longest Palindromic Substring: đối xứng là công cụ, không phải thủ thuật

Hầu hết bài toán chuỗi đều cho bạn một thuộc tính và yêu cầu tìm substring thỏa mãn nó. Bài này khác ở một điểm tinh tế: palindrome có cấu trúc nội tại. Mọi palindrome đều là phản chiếu của chính nó quanh một tâm. Tính chất cấu trúc đó là thứ giúp bạn thoát khỏi O(n^3) — không cần data structure phức tạp, chỉ cần nhận ra rằng bạn có thể mở rộng ra ngoài thay vì scan vào trong.

Đề bài

Cho một chuỗi s, tìm và trả về substring dài nhất đọc xuôi và ngược đều giống nhau; nếu có nhiều substring cùng độ dài tối đa, trả về một trong số đó đều được. Đề bài đầy đủ: LeetCode 5.

Ràng buộc:
- 1 <= s.length <= 1000
- s consist of only digits and English letters.

n <= 1000 thực sự nói lên điều gì

Đọc kỹ constraint này. n = 1000 cho phép O(n^2) thoải mái — một triệu phép tính, chạy trong vài millisecond. Nó làm O(n^3) trở nên nguy hiểm — một tỷ phép tính trong worst case, sẽ TLE trên LeetCode. Và nó làm thuật toán Manacher (O(n)) trở nên không cần thiết: bạn không cần giải pháp tuyến tính kỳ lạ đó ở đây.

Constraint đang nói đúng một điều: bạn cần O(n^2), và có hai cách đạt được — expand-from-center hoặc DP. Brute force ở mức O(n^3) dạy bạn thấy cấu trúc đúng bằng cách chỉ ra cái sai tốn bao nhiêu.

Tập ký tự (chữ số và chữ cái tiếng Anh) không ràng buộc thuật toán theo nghĩa nào quan trọng. Không có hash trick, không đếm alphabet. Chỉ là so sánh ký tự.

Approach 1: brute force

Kiểm tra mọi substring có thể. Với mỗi cặp (i, j), xác định s[i..j] có phải palindrome không, theo dõi cái dài nhất.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def is_palindrome(left: int, right: int) -> bool:
            while left < right:
                if s[left] != s[right]:
                    return False
                left += 1
                right -= 1
            return True
 
        n = len(s)
        longest = ""
 
        for i in range(n):
            for j in range(i, n):
                if is_palindrome(i, j) and j - i + 1 > len(longest):
                    longest = s[i:j + 1]
 
        return longest

public class Solution {
    public string LongestPalindrome(string s) {
        bool IsPalindrome(int left, int right) {
            while (left < right) {
                if (s[left] != s[right]) return false;
                left++;
                right--;
            }
            return true;
        }
 
        int n = s.Length;
        string longest = "";
 
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (IsPalindrome(i, j) && j - i + 1 > longest.Length) {
                    longest = s.Substring(i, j - i + 1);
                }
            }
        }
 
        return longest;
    }
}

Time: O(n^3). Có O(n^2) cặp (i, j), và is_palindrome scan tới O(n) ký tự mỗi lần. Space: O(1) không tính output string.

Sự lãng phí ở đây rõ ràng khi bạn nhìn kỹ. Khi kiểm tra s[0..4] có phải palindrome, bạn đang xem xét lại những ký tự mà bạn đã kiểm tra cho s[1..3], s[2..2], v.v. Mọi lần kiểm tra palindrome đều lặp lại công việc mà các lần kiểm tra trước đã làm. Đó là sự dư thừa mà DP loại bỏ và center-expansion hoàn toàn tránh được.

Approach 2: expand around centers

Mọi palindrome đều có một tâm. Palindrome độ dài lẻ ("aba", "racecar") có một ký tự duy nhất tại tâm. Palindrome độ dài chẵn ("abba", "bb") có khoảng trống giữa hai ký tự làm tâm. Trong chuỗi độ dài n, có đúng 2n - 1 tâm có thể: n tâm đơn-ký-tự và n - 1 tâm khoảng-trống.

Insight cốt lõi: thay vì hỏi "substring này có phải palindrome không?", hỏi "tôi có thể mở rộng từ tâm này được bao xa?" Bắt đầu từ tâm và mở rộng ra ngoài, mỗi lần mở rộng thành công thêm hai ký tự khớp nhau vào palindrome đã xác nhận. Bạn dừng ngay khi hai ký tự ngoài cùng không khớp. Tổng công việc trên tất cả 2n - 1 tâm là O(n^2), nhưng điều quan trọng là công việc bên trong không bị lặp lại.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def expand(left: int, right: int) -> str:
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            # left và right đã vượt quá một bước mỗi chiều
            return s[left + 1:right]
 
        if not s:
            return ""
 
        longest = ""
 
        for i in range(len(s)):
            # độ dài lẻ: tâm là ký tự i
            odd = expand(i, i)
            # độ dài chẵn: tâm là khoảng trống giữa i và i+1
            even = expand(i, i + 1)
 
            if len(odd) > len(longest):
                longest = odd
            if len(even) > len(longest):
                longest = even
 
        return longest

public class Solution {
    public string LongestPalindrome(string s) {
        string Expand(int left, int right) {
            while (left >= 0 && right < s.Length && s[left] == s[right]) {
                left--;
                right++;
            }
            // left và right đã vượt; palindrome thực sự là [left+1, right-1]
            return s.Substring(left + 1, right - left - 1);
        }
 
        if (string.IsNullOrEmpty(s)) return "";
 
        string longest = "";
 
        for (int i = 0; i < s.Length; i++) {
            string odd = Expand(i, i);
            string even = Expand(i, i + 1);
 
            if (odd.Length > longest.Length) longest = odd;
            if (even.Length > longest.Length) longest = even;
        }
 
        return longest;
    }
}

Time: O(n^2). Space: O(1) — chỉ một vài biến số nguyên và một tham chiếu đến substring tốt nhất tìm được, không có cấu trúc phụ trợ.

Trace tay: s = "babad"

Đi qua từng tâm:

i=0, tâm 'b':

• Odd expand: left=0, right=0. Ký tự khớp chính nó -> left=-1, right=1. Thoát vòng lặp. Kết quả: s[0:1] = "b" (độ dài 1).
• Even expand: left=0, right=1. s[0]='b', s[1]='a'. Không khớp. Kết quả: s[1:1] = "".

i=1, tâm 'a':

• Odd expand: left=1, right=1 -> khớp chính nó -> left=0, right=2. s[0]='b' == s[2]='b' -> left=-1, right=3. Thoát. Kết quả: s[0:3] = "bab" (độ dài 3).
• Even expand: left=1, right=2. s[1]='a', s[2]='b'. Không khớp. Kết quả: "".

i=2, tâm 'b':

• Odd expand: left=2, right=2 -> left=1, right=3. s[1]='a' == s[3]='a' -> left=0, right=4. s[0]='b' != s[4]='d' -> thoát. Kết quả: s[1:4] = "aba" (độ dài 3). Bằng với "bab".
• Even expand: s[2]='b', s[3]='a'. Không khớp. "".

i=3 và i=4: các expansion chỉ cho tối đa độ dài 1 và 2. Không cải thiện.

Kết quả cuối: "bab" (hoặc "aba" — cả hai đều hợp lệ, bài chấp nhận một trong hai).

Chi tiết quan trọng từ trace: hàm expand trả về s[left+1:right] vì vòng lặp thoát ra chỉ sau khi left và right đã vượt quá một bước. Tại điểm thoát, s[left] và s[right] là các ký tự không khớp đầu tiên (hoặc một trong chúng đã ra ngoài biên). Palindrome luôn nằm một bước bên trong.

Approach 3: dynamic programming

Cách đặt bài toán theo DP hỏi: khi nào s[i..j] là palindrome? Câu trả lời: khi s[i] == s[j] và s[i+1..j-1] cũng là palindrome. Recurrence đó định nghĩa một bảng hai chiều.

Gọi dp[i][j] = True nếu s[i..j] là palindrome. Base cases:

• Độ dài 1: dp[i][i] = True với mọi i.
• Độ dài 2: dp[i][i+1] = True khi và chỉ khi s[i] == s[i+1].

Sau đó điền bảng theo chiều tăng dần độ dài substring, từ 3 đến n.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n == 0:
            return ""
 
        # dp[i][j] = True nghĩa là s[i..j] là palindrome
        dp = [[False] * n for _ in range(n)]
        start = 0
        max_len = 1
 
        # mọi ký tự đơn đều là palindrome
        for i in range(n):
            dp[i][i] = True
 
        # substring độ dài 2
        for i in range(n - 1):
            if s[i] == s[i + 1]:
                dp[i][i + 1] = True
                start = i
                max_len = 2
 
        # độ dài từ 3 đến n
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                if s[i] == s[j] and dp[i + 1][j - 1]:
                    dp[i][j] = True
                    if length > max_len:
                        start = i
                        max_len = length
 
        return s[start:start + max_len]

public class Solution {
    public string LongestPalindrome(string s) {
        int n = s.Length;
        if (n == 0) return "";
 
        bool[,] dp = new bool[n, n];
        int start = 0, maxLen = 1;
 
        // mọi ký tự đơn
        for (int i = 0; i < n; i++)
            dp[i, i] = true;
 
        // substring độ dài 2
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                dp[i, i + 1] = true;
                start = i;
                maxLen = 2;
            }
        }
 
        // độ dài từ 3 đến n
        for (int length = 3; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                if (s[i] == s[j] && dp[i + 1, j - 1]) {
                    dp[i, j] = true;
                    if (length > maxLen) {
                        start = i;
                        maxLen = length;
                    }
                }
            }
        }
 
        return s.Substring(start, maxLen);
    }
}

Time: O(n^2) — điền bảng n x n với công việc hằng số mỗi ô. Space: O(n^2) cho bản thân bảng DP. Đó là chi phí: cùng time tiệm cận với expand-from-center, nhưng đổi O(1) space lấy O(n^2).

Bảng DP cho s = "babad" (5 x 5, các ô True được hiển thị):

Thứ tự điền: tất cả đường chéo độ dài 1 trước, rồi độ dài 2, rồi độ dài 3. dp[0][2] trở thành True vì s[0]='b' == s[2]='b' và dp[1][1]=True. dp[1][3] trở thành True vì s[1]='a' == s[3]='a' và dp[2][2]=True. Cả hai đều độ dài 3, nên đáp án là cái được cập nhật sau cùng — code chọn "aba" vì dp[1][3] là ô True độ dài 3 cuối cùng được ghi.

Các edge case

Một ký tự (s = "a"): expand với odd từ tâm 0 — ký tự khớp chính nó, vòng lặp chạy một lần rồi vượt biên, trả về "a". Với DP, khởi tạo độ dài 1 đặt dp[0][0] = True, max_len = 1, không tìm được độ dài nào lớn hơn.

Toàn ký tự giống nhau (s = "aaaa"): expand từ tâm 0 mở rộng sang phải càng xa càng tốt; từ tâm 1 mở rộng còn xa hơn. Kết quả cuối là toàn bộ chuỗi "aaaa". Với DP, mọi dp[i][j] đều True (vì s[i] == s[j] luôn đúng và substring bên trong là palindrome theo quy nạp). Entry cuối cùng được ghi cho độ dài tối đa bắt được toàn bộ chuỗi.

Không có palindrome dài hơn 1 (s = "abcde"): mọi expand chỉ trả về một ký tự (tâm) cho odd và chuỗi rỗng cho even. Kết quả dài nhất vẫn là độ dài 1 — đúng là ký tự đầu tiên.

Palindrome độ dài chẵn (s = "cbbd"): tâm quan trọng là khoảng trống giữa index 1 và 2 ('b' và 'b'). Even expand: left=1, right=2, s[1]='b' == s[2]='b' -> left=0, right=3. s[0]='c' != s[3]='d' -> thoát. Trả về s[1:3] = "bb". Đúng.

s độ dài 2, cả hai bằng nhau (s = "aa"): even expand tại i=0 cho "aa". Odd expand cho "a" mỗi ký tự. Kết quả là "aa".

s độ dài 2, khác nhau (s = "ab"): mọi expansion chỉ cho ký tự đơn. Kết quả là "a".

So sánh các approach

Pattern ẩn dưới cả hai approach tối ưu

Expand-from-center và recurrence DP đều là biểu hiện của cùng một sự thật: palindrome được định nghĩa theo recursion. Nếu s[i..j] là palindrome, bạn biết ngay s[i+1..j-1] cũng là palindrome. Tương đương, nếu bạn biết s[i+1..j-1] là palindrome, bạn chỉ cần s[i] == s[j] để mở rộng ra ngoài.

Expand-from-center xây dựng trên điều này bằng cách làm việc từ ngoài vào trong từ độ dài 1: mở rộng cho đến khi không thể. DP xây dựng từ định nghĩa theo hướng ngược lại: điền các case nhỏ trước, rồi dùng chúng để xác nhận các case lớn hơn. Cùng recurrence, hướng tính toán ngược nhau.

Pattern này gọi là "center-anchored palindrome expansion" và nó chuyển trực tiếp sang các bài anh em dưới đây. Khi thấy câu hỏi về palindrome, instinct đầu tiên nên là: xác định tâm, nghĩ về expansion. Substring là đơn vị phân tích sai; tâm là đơn vị đúng.

Cái tôi thực sự sẽ dùng trong production

Expand-from-center. Không phải bàn cãi. Nó có cùng O(n^2) time như DP và O(1) space thay vì O(n^2). Code ngắn hơn và logic dễ giải thích hơn trong phỏng vấn: "Tôi coi mỗi vị trí như một tâm tiềm năng và mở rộng ra ngoài." Bảng DP đúng và có giá trị sư phạm — nó xây dựng intuition cho tabulation — nhưng nó trả n^2 memory cho thứ bạn không thực sự cần lúc runtime.

Brute force là điểm khởi đầu đúng khi bạn bị stuck: implement nó, xác nhận nó chạy đúng, rồi xác định sự dư thừa. Khoảng cách từ O(n^3) xuống O(n^2) chính xác là một insight: ngừng kiểm tra substring và bắt đầu nghĩ về tâm.

Vị trí trong series DP và những gì sẽ đến tiếp theo

Đây là bài thứ năm trong series dynamic-programming, sau Climbing Stairs, House Robber, và Coin Change. Những bài trước đó đều có state một chiều — một index tiến qua cấu trúc tuyến tính. Longest Palindromic Substring giới thiệu DP state hai chiều: dp[i][j] phụ thuộc vào dp[i+1][j-1]. Dependency chéo đó là điều mới ở đây, và nó xuất hiện lại trong vài bài tiếp theo.

Palindromic Substrings (LeetCode 647) là extension trực tiếp nhất. Cùng setup, câu hỏi khác: thay vì palindrome dài nhất, đếm tất cả chúng. Cấu trúc expand-from-center giống hệt nhau — bạn chỉ đếm mỗi lần expansion thành công thay vì so sánh độ dài. Nếu bài này cảm thấy tự nhiên, 647 chỉ mất năm phút.

Longest Palindromic Subsequence (LeetCode 516) thay đổi luật chơi: các ký tự không cần liên tiếp nữa. Bây giờ dp[i][j] là độ dài subsequence palindrome dài nhất trong s[i..j]. Recurrence: nếu s[i] == s[j], thì dp[i][j] = dp[i+1][j-1] + 2; ngược lại dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Thứ tự điền chéo từ bài này áp dụng trực tiếp.

Shortest Palindrome (LeetCode 214) hỏi: số ký tự tối thiểu cần thêm vào đầu s để biến nó thành palindrome là bao nhiêu? Insight là tìm palindromic prefix dài nhất, là phiên bản bị ràng buộc của bài này.

Edit Distance (LeetCode 72) cũng điền bảng DP 2D với dependency chéo và lân cận — không phải palindrome, nhưng cùng cấu trúc không gian. Thấy dp[i][j] phụ thuộc dp[i+1][j-1] ở đây xây dựng intuition cho cách Edit Distance được điền.