201041: [AtCoder]ARC104 B - DNA Sequence
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
, andG
.
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 toCG
, which is a permutation ofGC
.AGCT
(the $1$-st through $4$-th characters) is complementary toTCGA
, which is a permutation ofAGCT
.
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 toTA
, which is a permutation ofAT
.TA
(the $2$-st through $3$-rd characters) is complementary toAT
, which is a permutation ofTA
.AT
(the $3$-rd through $4$-th characters) is complementary toTA
, which is a permutation ofAT
.ATAT
(the $1$-st through $4$-th characters) is complementary toTATA
, which is a permutation ofATAT
.
Sample Input 3
10 AAATACCGCG
Sample Output 3
6