Contest Duration: - (local time) (120 minutes) Back to Home
B - DNA Sequence /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

A, T, C, G から成る長さ N の文字列 S があります。

S の連続する空でない部分文字列 T であって、次の条件を満たすものの個数を求めてください。

• T と相補的であるような、T の文字を並び替えた文字列が存在する。

ただし、文字列として同じであっても S 内の位置が異なれば違う部分列とみなします。

制約

• 1 \leq N \leq 5000
• SA, T, C, G のみから成る

N S

出力

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

4 AGCT

出力例 1

2

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

4 ATAT

出力例 2

4

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

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.

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.

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.

10 AAATACCGCG

6