Ý tưởng

Duyệt qua ~j~, ta sẽ chọn ~i~ từ ~1~ đến ~j-1~ để thực hiện phép lật, dễ thấy khi lật đoạn ~S_i...S_j~ có ~S_i = S_j (i <= j)~ thì cho cùng kết quả khi lật đoạn ~S_{i+1}...S_{j-1}~, và thế sẽ bị lặp lại chuỗi đã xuất hiện.

Từ đó ta có số chuỗi trong tập ~M = \frac{n \times (n-1)}{2} + 1 - ~ số cặp ~(i, j)~ có ~S_i = S_j~ (~n~ là độ dài của xâu ~S~).

Đếm số cặp ~(i, j)~ thỏa tính chất trên, ta duyệt qua ~j~ và cập nhật kết quả vào mảng ~cnt_{S_j}~ như sau.

ll res = 0;
for(char &c : s) {
    int x = c - 'a';
    res += cnt[x]++;
}