分数: 333 分
问题陈述
高桥录制了一段由以下内容组成的旋律 N 注释作为字符串 S.
的 i- 第一个字符 S_i of S 是一个大写英文字母(A–Z),代表 i- 第一个音符。
对于字符串 X, 压缩序列 of X 定义如下。
扫描字符 X 从头开始:始终保留第一个字符,对于每个后续字符,仅当它与最后一个保留的字符不同时才保留它。得到的字符串称为压缩序列 X.
在压缩序列中,任何两个相邻的字符都是不同的。
例如,压缩序列 AAABBBAA is ABA,以及压缩序列 ABCABC is ABCABC.
对于一对整数 (l, r) 满意 1 \le l \le r \le N,考虑连续子串的压缩序列 S_l S_{l+1} \dots S_r of S.
如果这个压缩序列的长度正好是 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
- 第一行包含一个整数 N 代表旋律的长度。
- 第二行包含一个字符串 S 长度 N 由大写英文字母组成。
输出
在一行中打印三明治间隔的数量。
样本输入 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