Строка \(t_1t_2 \dots t_k\) является хорошей, если каждый символ этой строки принадлежит хотя бы одному палиндрому длины больше 1.
Палиндром — это строка, читающаяся одинаково от первого символа к последнему и от последнего символа к первому. Например, строки A, BAB, ABBA, BAABBBAAB являются палиндромами, а строки AB, ABBBAA, BBBA — нет.
Например, хорошим являются строки:
- \(t\) = AABBB (символы \(t_1\), \(t_2\) принадлежат палиндрому \(t_1 \dots t_2\), а символы \(t_3\), \(t_4\), \(t_5\) — палиндрому \(t_3 \dots t_5\));
- \(t\) = ABAA (символы \(t_1\), \(t_2\), \(t_3\) принадлежат палиндрому \(t_1 \dots t_3\), а символ \(t_4\) — палиндрому \(t_3 \dots t_4\));
- \(t\) = AAAAA (все символы принадлежат палиндрому \(t_1 \dots t_5\));
Вам задана строка \(s\) длины \(n\), состоящая только из букв A и B.
Посчитайте количество хороших подстрок строки \(s\).
Примечание
Первая строка содержит шесть хороших подстрок: \(s_1 \dots s_2\), \(s_1 \dots s_4\), \(s_1 \dots s_5\), \(s_3 \dots s_4\), \(s_3 \dots s_5\) и \(s_4 \dots s_5\).
Вторая строка содержит две хороших подстроки: \(s_1 \dots s_2\), \(s_1 \dots s_3\) and \(s_2 \dots s_3\)