/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 333 点
問題文
高橋君は、N 音からなるメロディを文字列 S として記録した。
S の i 文字目 S_i は大文字英字（A–Z）であり、i 番目の音を表す。
文字列 X に対し、X の 圧縮列 を次のように定義する。
X の文字を先頭から順に見ていき、最初の文字は常に残し、2 文字目以降は直前に残した文字と異なる場合のみ残すことで得られる文字列を、X の圧縮列と呼ぶ。
圧縮列では隣接する 2 文字は互いに異なる。
たとえば、AAABBBAA の圧縮列は ABA であり、ABCABC の圧縮列は ABCABC である。
1 \le l \le r \le N を満たす整数の組 (l, r) に対し、S の連続部分文字列 S_l S_{l+1} \dots S_r の圧縮列を考える。
この圧縮列の長さがちょうど 3 であり、かつその 1 文字目と 3 文字目が等しいとき、区間 [l, r] を サンドイッチ区間 と呼ぶ。
たとえば、ある区間に対応する連続部分文字列が AABBA であるとき、その圧縮列は ABA で、長さが 3 かつ 1 文字目と 3 文字目が等しいため、この区間はサンドイッチ区間である。
一方、連続部分文字列が ABC であるとき、圧縮列は ABC で長さは 3 だが 1 文字目と 3 文字目が異なるため、サンドイッチ区間ではない。
また、連続部分文字列が ABAB であるとき、圧縮列は ABAB で長さが 4 であるため、サンドイッチ区間ではない。
サンドイッチ区間の個数を求めてください。
制約
- 1 \le N \le 10^6
- S は長さ N の大文字英字（
A–Z）からなる文字列である。
入力
N S
- 1 行目には、メロディの長さを表す整数 N が与えられる。
- 2 行目には、長さ N の大文字英字からなる文字列 S が与えられる。
出力
サンドイッチ区間の個数を 1 行で出力せよ。
入力例 1
5 AABBA
出力例 1
2
入力例 2
3 ABC
出力例 2
0
入力例 3
25 AAABBAAAACCCAABBBADDDDAAA
出力例 3
25
入力例 4
75 AAAAABBBBAAAAAACCCDDDDDCCCCEEFFFFFFFEEEEEGGGGGGHHHGGGGIIIIIJJJJIIIIIIIKKKKK
出力例 4
111
入力例 5
1 A
出力例 5
0
Score : 333 pts
Problem Statement
Takahashi recorded a melody consisting of N notes as a string S.
The i-th character S_i of S is an uppercase English letter (A–Z), representing the i-th note.
For a string X, the compressed sequence of X is defined as follows.
Scan the characters of X from the beginning: always keep the first character, and for each subsequent character, keep it only if it differs from the last kept character. The resulting string is called the compressed sequence of X.
In a compressed sequence, any two adjacent characters are distinct.
For example, the compressed sequence of AAABBBAA is ABA, and the compressed sequence of ABCABC is ABCABC.
For a pair of integers (l, r) satisfying 1 \le l \le r \le N, consider the compressed sequence of the contiguous substring S_l S_{l+1} \dots S_r of S.
If the length of this compressed sequence is exactly 3 and its 1st and 3rd characters are equal, then the interval [l, r] is called a sandwich interval.
For example, if the contiguous substring corresponding to some interval is AABBA, its compressed sequence is ABA, which has length 3 and equal 1st and 3rd characters, so this interval is a sandwich interval.
On the other hand, if the contiguous substring is ABC, its compressed sequence is ABC, which has length 3 but the 1st and 3rd characters differ, so it is not a sandwich interval.
Also, if the contiguous substring is ABAB, its compressed sequence is ABAB, which has length 4, so it is not a sandwich interval.
Find the number of sandwich intervals.
Constraints
- 1 \le N \le 10^6
- S is a string of length N consisting of uppercase English letters (
A–Z).
Input
N S
- The first line contains an integer N representing the length of the melody.
- The second line contains a string S of length N consisting of uppercase English letters.
Output
Print the number of sandwich intervals in one line.
Sample Input 1
5 AABBA
Sample Output 1
2
Sample Input 2
3 ABC
Sample Output 2
0
Sample Input 3
25 AAABBAAAACCCAABBBADDDDAAA
Sample Output 3
25
Sample Input 4
75 AAAAABBBBAAAAAACCCDDDDDCCCCEEFFFFFFFEEEEEGGGGGGHHHGGGGIIIIIJJJJIIIIIIIKKKKK
Sample Output 4
111
Sample Input 5
1 A
Sample Output 5
0