Строка $$$t_1t_2 \dots t_k$$$ является хорошей, если каждый символ этой строки принадлежит хотя бы одному палиндрому длины больше 1.
Палиндром — это строка, читающаяся одинаково от первого символа к последнему и от последнего символа к первому. Например, строки A, BAB, ABBA, BAABBBAAB являются палиндромами, а строки AB, ABBBAA, BBBA — нет.
Например, хорошим являются строки:
Вам задана строка $$$s$$$ длины $$$n$$$, состоящая только из букв A и B.
Посчитайте количество хороших подстрок строки $$$s$$$.
Первая строка содержит число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — длину строки $$$s$$$.
Вторая строка содержит строку $$$s$$$, состоящую из букв A и B.
Выведите одно число — количество хороших подстрок строки $$$s$$$.
5 AABBB
6
3 AAA
3
7 AAABABB
15
Первая строка содержит шесть хороших подстрок: $$$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$$$
Название |
---|