AT_arc104_b [ARC104B] DNA Sequence

[problemUrl]: https://atcoder.jp/contests/arc104/tasks/arc104_b `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` のみから成る ### 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` と相補的です。