/
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
A, B, C からなる長さ N の文字列 S が与えられます。
S を 2 箇所で区切り、3 つの空でない部分文字列に分割します。形式的には、S の k 文字目を S_k とし、1 \leq i < j < N なる整数の組 (i, j) を選び、S を S_1S_2 \ldots S_i, S_{i + 1}S_{i + 2} \ldots S_j, S_{j + 1}S_{j + 2} \ldots S_N の 3 つの部分文字列に分割します。
3 つの部分文字列それぞれが A, B, C をすべて含むような区切り方の個数を求めてください。
制約
- 3 \leq N \leq 3 \times 10^5
- N は整数
- S は
A,B,Cからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
答えを出力せよ。
入力例 1
12 AABCCABCCBCA
出力例 1
5
| により文字列を区切る位置を表すことにすると、AABC|CAB|CCBCA, AABC|CABC|CBCA, AABC|CABCC|BCA, AABCC|ABC|CBCA, AABCC|ABCC|BCA の 5 通りの区切り方があります。
入力例 2
3 ABC
出力例 2
0
入力例 3
20 BCACABCACACABCAACBCA
出力例 3
65
Score : 400 points
Problem Statement
You are given a string S of length N consisting of A, B, and C.
We split S at two positions to divide it into three non-empty substrings. Formally, let S_k denote the k-th character of S; we choose a pair of integers (i, j) such that 1 \leq i < j < N, and divide S into three substrings S_1S_2 \ldots S_i, S_{i + 1}S_{i + 2} \ldots S_j, and S_{j + 1}S_{j + 2} \ldots S_N.
Find the number of ways to split S such that each of the three substrings contains all of A, B, and C.
Constraints
- 3 \leq N \leq 3 \times 10^5
- N is an integer.
- S is a string of length N consisting of
A,B, andC.
Input
The input is given from Standard Input in the following format:
N S
Output
Print the answer.
Sample Input 1
12 AABCCABCCBCA
Sample Output 1
5
Using | to denote the positions where the string is split, there are five ways to split it: AABC|CAB|CCBCA, AABC|CABC|CBCA, AABC|CABCC|BCA, AABCC|ABC|CBCA, and AABCC|ABCC|BCA.
Sample Input 2
3 ABC
Sample Output 2
0
Sample Input 3
20 BCACABCACACABCAACBCA
Sample Output 3
65