CF1238D AB-string

如果字符串 $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$）； 现在给定一个长度为 $n$ 仅由字母 A 和 B 组成的字符串 $s$。 请你计算字符串 $s$ 的“好”子串的数量。

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$），表示字符串 $s$ 的长度。 第二行包含字符串 $s$，仅由字母 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$ 和 $s_2\dots s_3$。 由 ChatGPT 4.1 翻译