← 返回题目列表

AtCoder · awc0071_b

B. 三明治旋律

中文机器翻译题面 查看原题

分数: 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