AT_arc104_b [ARC104B] DNA Sequence

有一个由 `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 \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 翻译