🎯 Mục tiêu

• Hiểu chuỗi đối xứng (Palindrome).
• Biết cách kiểm tra và tìm chuỗi đối xứng dài nhất.
• Làm quen kỹ thuật mở rộng hai con trỏ.

📘 1️⃣ Kiểm tra Palindrome

def is_pal(s):
    return s == s[::-1]

📘 2️⃣ Tìm Palindrome dài nhất – Expand Around Center

Mỗi vị trí có thể là tâm (lẻ hoặc chẵn). Mở rộng trái phải đến khi không còn khớp.

🌿 Python

def longest_pal(s):
    res=""
    for i in range(len(s)):
        # tâm lẻ
        l=r=i
        while l>=0 and rlen(res): res=s[l:r+1]
            l-=1; r+=1
        # tâm chẵn
        l,r=i,i+1
        while l>=0 and rlen(res): res=s[l:r+1]
            l-=1; r+=1
    return res
print(longest_pal("babad"))

🌿 C++

string longestPal(string s){
    int n=s.size(),start=0,len=1;
    for(int i=0;i=0&&rlen){len=r-l+1;start=l;}
            l--;r++;
        }
        l=i;r=i+1;
        while(l>=0&&rlen){len=r-l+1;start=l;}
            l--;r++;
        }
    }
    return s.substr(start,len);
}

🧩 Bài tập

1. Liệt kê tất cả các palindrome trong chuỗi.
2. Tìm palindrome dài nhất ≤ k ký tự.
3. Đếm số chuỗi con đối xứng trong S.

# Duyệt mọi tâm, đếm mỗi khi s[l]==s[r]
count += 1 mỗi lần mở rộng hợp lệ