B - DNA Sequence 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

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

入力例 1

4 AGCT

出力例 1

2

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

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

入力例 2

4 ATAT

出力例 2

4

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

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

入力例 3

10 AAATACCGCG

出力例 3

6

Score : 400 points

Problem Statement

We have a string S of length N consisting of A, T, C, and G.

Strings T_1 and T_2 of the same length are said to be complementary when, for every i (1 \leq i \leq l), the i-th character of T_1 and the i-th character of T_2 are complementary. Here, A and T are complementary to each other, and so are C and G.

Find the number of non-empty contiguous substrings T of S that satisfies the following condition:

  • There exists a string that is a permutation of T and is complementary to T.

Here, we distinguish strings that originate from different positions in S, even if the contents are the same.

Constraints

  • 1 \leq N \leq 5000
  • S consists of A, T, C, and G.

Input

Input is given from Standard Input in the following format:

N S

Output

Print the number of non-empty contiguous substrings T of S that satisfies the condition.

Sample Input 1

4 AGCT

Sample Output 1

2

The following two substrings satisfy the condition:

  • GC (the 2-nd through 3-rd characters) is complementary to CG, which is a permutation of GC.
  • AGCT (the 1-st through 4-th characters) is complementary to TCGA, which is a permutation of AGCT.

Sample Input 2

4 ATAT

Sample Output 2

4

The following four substrings satisfy the condition:

  • AT (the 1-st through 2-nd characters) is complementary to TA, which is a permutation of AT.
  • TA (the 2-st through 3-rd characters) is complementary to AT, which is a permutation of TA.
  • AT (the 3-rd through 4-th characters) is complementary to TA, which is a permutation of AT.
  • ATAT (the 1-st through 4-th characters) is complementary to TATA, which is a permutation of ATAT.

Sample Input 3

10 AAATACCGCG

Sample Output 3

6