# 1. Tóm tắt đề bài

Cho string s, tìm số lượng string palindrome có độ dài bằng $3$ khác nhau có thể tạo ra từ những subsequence của s.

### Giới hạn

$1 \le n \le 10^5$

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

**Độ phức tạp dự tính: $O(26*n)$**

# 3. Lời giải chi tiết

Nhận thấy tính chất của một string palindrome có độ dài bằng $3$ là phần tử đầu và cuối giống nhau còn ở giữa thế nào cũng được và nhận thấy đáp án tối đa của bài là $26*26$. Ta có thể cố định $2$ đầu của string và tìm số lượng phần tử ở giữa thỏa mãn.

Xét tuần tự các chữ cái từ a->z làm $2$ đầu của xâu palindrome. Ta nhận thấy số xâu palindrome khác nhau tạo được từ việc cố định trên chính là số chữ cái khác nhau giữa các chữ cái được cố định làm $2$ đầu.

Vì vậy, với việc cố định từ a->z, ta tìm vị trí đầu tiên và cuối cùng của chữ cái ta cố định và kiểm tra xem giữa $2$ vị trí đó có bao nhiêu chữ cái khác nhau.

Để kiểm tra xem có bao nhiêu chữ cái khác nhau thì có thể sử dụng một số cấu trúc dữ liệu như set hay map hoặc dùng mảng bool, cái này phụ thuộc vào bạn.

### Độ phức tạp thuật toán

Thời gian: $O(26*n)$

Bộ nhớ mở rộng: $O(n)$