← 返回题目列表

AtCoder · abc455_e

H. 不平衡 ABC 子串

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

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