题目描述

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$ であって、条件を満たすものの個数を出力せよ。

题目大意

题目翻译

我们有一条长度为 $N$ 的 DNA（由 A、C、G、T 四个字母组成的一条链），定义为 $S$。

定义两个字符匹配当且仅当这两个字符为 A,T 或 C,G 时匹配。

你需要找到 $S$ 中非空子串 $T$ 的数量，使得对于每一个 $T$，都有一个 $T'$ 是 $T$ 的排列，并且和 $T$ 一一配对。

对于不同位置上的 $T$，即便内容相同，也计两次。

样例解释

样例 1 解释

两个 $T$ 为 GC 和 ACGT。

样例 2 解释

四个 $T$ 分别 AT（两个）、TA 和 ATAT。

数据范围与约定

对于 $100\%$ 的数据，$1\leq N\leq 5000$，$S$ 中只含有 A、C、G、T。

4 AGCT

2

4 ATAT

4

10 AAATACCGCG

6

提示

制約

• $1\ \leq\ N\ \leq\ 5000$
• $S$ は A, T, C, G のみから成る

Sample Explanation 1

次の $2$ つの部分文字列が条件を満たします。 - GC ($2$ 文字目から $3$ 文字目) は、これを並び替えた CG と相補的です。 - AGCT ($1$ 文字目から $4$ 文字目) は、これを並び替えた TCGA と相補的です。

Sample Explanation 2

次の $4$ つの部分文字列が条件を満たします。 - AT ($1$ 文字目から $2$ 文字目) は、これを並び替えた TA と相補的です。 - TA ($2$ 文字目から $3$ 文字目) は、これを並び替えた AT と相補的です。 - AT ($3$ 文字目から $4$ 文字目) は、これを並び替えた TA と相補的です。 - ATAT ($1$ 文字目から $4$ 文字目) は、これを並び替えた TATA と相補的です。