Bài toán
Cho chuỗi s, hãy đếm, có bao nhiêu chuỗi con là palindrome.
Chuỗi con trùng nhau về nội dung nhưng khác vị trí vẫn tính là khác nhau.
Ví dụ:
text:
Input: s = "abc"
Output: 3 ("a", "b", "c")
Input: s = "aaa"
Output: 6 ("a", "a", "a", "aa", "aa", "aaa")Phân Tích & Tiếp Cận
Expand Around Center
Tương tự bài trước, ta duyệt qua tất cả các tâm.
Mỗi lần mở rộng thành công (s[l] == s[r]), nghĩa là ta tìm thêm được 1 chuỗi palindrome mới. Ta chỉ cần tăng biến count.
typescript:
function countSubstrings(s: string): number {
let count = 0;
for (let i = 0; i < s.length; i++) {
// Odd length palindromes
count += countPals(i, i);
// Even length palindromes
count += countPals(i, i + 1);
}
function countPals(l: number, r: number): number {
let res = 0;
while (l >= 0 && r < s.length && s[l] === s[r]) {
res++;
l--;
r++;
}
return res;
}
return count;
}- Time Complexity: $O(n^2)$.
- Space Complexity: $O(1)$.
Pattern Nhận Diện
Hai bài toán Palindrome này gần như là "sinh đôi". Nắm vững kỹ thuật Expand Around Center là giải quyết được cả hai một cách tối ưu.