题目描述

有一个由 A、T、C、G 组成的长度为 $N$ 的字符串 $S$。

长度相等的字符串 $T_1$、$T_2$ 被称为“互补的”，当 $|T_1| = l$ 时，对于任意 $1 \leq i \leq l$，$T_1$ 和 $T_2$ 的第 $i$ 个字符的组合要么是（A 和 T），要么是（C 和 G）的组合（例如，A 和 T 的组合时，无论哪个字符属于 $T_1$ 都可以）。

请计算 $S$ 的所有连续且非空的子串 $T$ 中，满足以下条件的子串个数：

• 存在一个将 $T$ 的字符重新排列后的字符串，使其与 $T$ 互补。

注意，即使字符串内容相同，只要在 $S$ 中的位置不同，也视为不同的子串。

输入格式

输入以如下格式从标准输入读入：

$N$ $S$

输出格式

输出 $S$ 的所有连续且非空的子串 $T$ 中，满足条件的子串个数。

样例 1

输入

4 AGCT

输出

2

样例 2

输入

4 ATAT

输出

4

样例 3

输入

10 AAATACCGCG

输出

6

说明/提示

限制条件

• $1 \leq N \leq 5000$
• $S$ 仅由 A、T、C、G 组成

样例解释 1

有如下 $2$ 个子串满足条件：

• GC（第 $2$ 个字符到第 $3$ 个字符），将其重新排列为 CG 后是互补的。
• AGCT（第 $1$ 个字符到第 $4$ 个字符），将其重新排列为 TCGA 后是互补的。

样例解释 2

有如下 $4$ 个子串满足条件：

• AT（第 $1$ 个字符到第 $2$ 个字符），将其重新排列为 TA 后是互补的。
• TA（第 $2$ 个字符到第 $3$ 个字符），将其重新排列为 AT 后是互补的。
• AT（第 $3$ 个字符到第 $4$ 个字符），将其重新排列为 TA 后是互补的。
• ATAT（第 $1$ 个字符到第 $4$ 个字符），将其重新排列为 TATA 后是互补的。

由 ChatGPT 4.1 翻译