647. Palindromic Substrings
Tags:
Medium
Skills:
String
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu đến số lượng substring là palindrome trong một chuỗi s. Một substring là palindrome nếu đọc xuôi và ngược đều giống nhau
Approach - Expand around center
Với mỗi vị trí (và cặp vị trí liền kề) trong chuỗi, mở rộng ra hai phía để kiểm tra các palindrome có tâm tại đó. Cách này có TC O(n^2) nhưng rất dễ cài đặt và chạy tốt với n ≤ 1000
Time and space complexity
Solution
1function countSubstrings(s: string): number {
2 let count =0;
3 const n = s.length;
4
5 for(let center = 0; center < 2 * n - 1; center++) {
6 let left = Math.floor(center /2 );
7 let right = left + (center % 2);
8 while(left >=0 && right < n && s[left] === s[right]) {
9 count++;
10 left--;
11 right++
12 }
13 }
14 return count;
15};let right = left + (center % 2);Công thức let right = left + (center % 2); xuất hiện trong phương pháp "Expand Around Center" để duyệt qua tất cả các tâm có thể của palindrome trong chuỗi. Mục đích là xét cả hai trường hợp:
Cụ thể:
center từ 0 đến 2 * n - 2 (với n là độ dài chuỗi), ta tính:left = Math.floor(center / 2);right = left + (center % 2);Ý nghĩa:
center là số chẵn (center % 2 == 0), thì left == right ⇒ kiểm tra palindrome lẻ với tâm tại một ký tự (ví dụ: expandAroundCenter(i, i)).center là số lẻ (center % 2 == 1), thì right = left + 1 ⇒ kiểm tra palindrome chẵn với tâm nằm giữa hai ký tự (ví dụ: expandAroundCenter(i, i+1)).Cách làm này giúp duyệt qua tất cả các tâm palindrome (cả lẻ và chẵn) chỉ với một vòng lặp, thay vì phải viết hai vòng lặp riêng biệt cho từng loại độ dài.
let left = Math.floor(center / 2);Công thức let left = Math.floor(center / 2); xuất phát từ cách mã hóa tất cả các tâm có thể của palindrome (bao gồm cả tâm lẻ và tâm chẵn) thành một chỉ số duy nhất là center. Đây là ý tưởng của phương pháp "Expand Around Center" để tránh phải viết hai vòng lặp riêng biệt cho từng loại tâm.
Giải thích chi tiết:
Khi duyệt center từ 0 đến 2n−2:
center chẵn (ví dụ 0, 2, 4,...):left = right = center / 2.center lẻ (ví dụ 1, 3, 5,...):left = (center - 1) / 2, right = left + 1.Khi dùng công thức:
left = Math.floor(center / 2)right = left + (center % 2)Ta sẽ thu được:
center chẵn: right = left (tâm lẻ)center lẻ: right = left + 1 (tâm chẵn)Như vậy, công thức này giúp ánh xạ chỉ số center thành cặp chỉ số left và right phù hợp để mở rộng palindrome quanh tâm đó, bao phủ tất cả các trường hợp palindrome lẻ và chẵn một cách gọn gàng