分数: 450 点
问题陈述
给你一个字符串 S 长度 N 由三个字符组成 A, B,和 C.
有 \frac{N(N+1)}{2} 的非空子串 S;找出其中有多少满足以下条件:
- 出现的次数
A,B,和C彼此不同。
如果两个子串取自不同位置,则分别计算它们 S,即使它们与字符串相同。
什么是子串?
A 子字符串 of S 是从开头删除零个或多个字符,从结尾删除零个或多个字符得到的字符串 S。 例如,AB 是一个子串 ABC,但是 AC 不是以下的子串 ABC.
约束
- 1 \leq N \leq 2 \times 10^5
- |S|=N
- N 是一个整数。
- S 是由三个字符组成的字符串
A,B,和C.
输入
输入由标准输入按以下格式给出:
N S
输出
在一行上输出答案。
样本输入 1
6 AABBCC
示例输出 1
4
删除 0 开头的字符和 3 结尾的字符 S 给出 AAB,满足条件。
删除 1 字符从开头和 2 结尾的字符 S 给出 ABB,满足条件。
删除 2 开头的字符和 1 结尾的字符 S 给出 BBC,满足条件。
删除 3 开头的字符和 0 结尾的字符 S 给出 BCC,满足条件。
没有其他子字符串满足条件。
示例输入 2
6 ABCABC
示例输出 2
0
没有子字符串满足条件。
示例输入 3
10 ACABCAABAB
示例输出 3
17