Daily 10/02/2024: [647. Palindromic Substrings](https://leetcode.com/problems/palindromic-substrings/)

# 1. Tóm tắt đề bài
Cho một chuỗi ```s```, trả về số lượng chuỗi con **palindrome** trong chuỗi đó.
Một chuỗi được gọi là **palindrome** khi nó đọc xuôi và đọc ngược giống nhau. Chuỗi con là một chuỗi ký tự liền kề nhau trong chuỗi.

#### Giới hạn
- $1 \le$ ```s.length``` $\le 1000$
- ```s``` chỉ gồm các chữ cái tiếng anh thường.

# 2. Tóm tắt lời giải

#### Phân tích
- Đầu tiên chúng ta hãy nghĩ tới thuật toán chạy trâu, về cơ bản là chúng ta sẽ kiểm tra từng đoạn trong chuỗi xong kiểm tra chuỗi đó có phải palindrome rồi đếm. Như vậy thì độ phức tạp sẽ lên tới $O(n^3)$.
- Chúng ta sẽ cải thiện bằng cách xét từng vị trí 1 và lan rộng ra hai bên như vậy độ phức tạp sẽ giảm xuống $O(n^2)$.
- Thôi thế thôi, còn với ai yêu thích dp thì tự nghiên cứu nhé! Chúc năm mới mọi người vui vẻ.
# 3. Lời giải chi tiết

#### Code

class Solution:
    def countSubstrings(self, s: str) -> int:
        n, ans = len(s), 0
        
        def palindromeCount(left: int, right: int) -> int:
            count = 0
            while left >= 0 and right < n and s[left] == s[right]:
                left -= 1
                right += 1
                count += 1
            return count
        
        for i in range(n):
            even = palindromeCount(i, i + 1)
            odd = palindromeCount(i, i)
            ans += even + odd
            
        return ans

#### Độ phức tạp
$O(n^2)$
# 4. Kết luận & gợi ý mở rộng
- Năm mới vui vẻ chill chill.
-

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Hash Map</span>