201041: [AtCoder]ARC104 B - DNA Sequence

Memory Limit:1024 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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

Input

题意翻译

### 题目翻译 我们有一条长度为 $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`。

加入题单

上一题 下一题 算法标签: