Longest Palindromic Substring

Bài toán

Cho chuỗi s, tìm chuỗi con đối xứng (palindrome) dài nhất trong s.

Ví dụ:

Input: s = "babad"
Output: "bab" hoặc "aba"

Phân Tích & Tiếp Cận

Cách 1: Brute Force

Duyệt mọi chuỗi con ($O(n^2)$), kiểm tra từng cái ($O(n)$) -> Tổng $O(n^3)$. Quá chậm.

Cách 2: Dynamic Programming ($O(n^2)$)

dp[i][j] = true nếu s[i...j] là palindrome.

Cách 3: Expand Around Center (Trung tâm mở rộng) - Tốt hơn về Space

Một palindrome luôn đối xứng qua tâm.

• Tâm có thể là 1 ký tự (vd "aba", tâm b).
• Tâm có thể là 2 ký tự (vd "abba", tâm bb). Với chuỗi độ dài N, có 2N - 1 tâm. Ta duyệt qua từng tâm và cố gắng mở rộng ra hai bên left-- và right++ chừng nào chúng còn giống nhau.

function longestPalindrome(s: string): string {
    let res = "";
    let resLen = 0;

    for (let i = 0; i < s.length; i++) {
        // Trường hợp 1: Tâm lẻ (Odd length)
        expand(i, i);
        
        // Trường hợp 2: Tâm chẵn (Even length)
        expand(i, i + 1);
    }

    function expand(l: number, r: number) {
        while (l >= 0 && r < s.length && s[l] === s[r]) {
            if (r - l + 1 > resLen) {
                res = s.substring(l, r + 1);
                resLen = r - l + 1;
            }
            l--;
            r++;
        }
    }

    return res;
}

• Time Complexity: $O(n^2)$.
• Space Complexity: $O(1)$ (Nếu không tính string kết quả).

Pattern Nhận Diện

• Bài toán Palindrome thường giải bằng 2 cách: DP (bảng $N \times N$) hoặc Expand from Center. Expand from center thường tiết kiệm bộ nhớ hơn.