配点 : $400$ 点

問題文

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$ 内の位置が異なれば違う部分列とみなします。

制約

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

入力

入力は以下の形式で標準入力から与えられる。

$N$ $S$

出力

$S$ の連続する空でない部分文字列 $T$ であって、条件を満たすものの個数を出力せよ。

4 AGCT

2

次の $2$ つの部分文字列が条件を満たします。

• GC ($2$ 文字目から $3$ 文字目) は、これを並び替えた CG と相補的です。
• AGCT ($1$ 文字目から $4$ 文字目) は、これを並び替えた TCGA と相補的です。

4 ATAT

4

次の $4$ つの部分文字列が条件を満たします。

• AT ($1$ 文字目から $2$ 文字目) は、これを並び替えた TA と相補的です。
• TA ($2$ 文字目から $3$ 文字目) は、これを並び替えた AT と相補的です。
• AT ($3$ 文字目から $4$ 文字目) は、これを並び替えた TA と相補的です。
• ATAT ($1$ 文字目から $4$ 文字目) は、これを並び替えた TATA と相補的です。

10 AAATACCGCG

6