E - Unbalanced ABC Substrings Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

A, B, C の 3 種類の文字のみからなる長さ N の文字列 S が与えられます。
S の空でない部分文字列は \frac{N(N+1)}{2} 個ありますが、そのうち以下の条件を満たすものがいくつあるか求めてください。

  • A, B, C の出現回数が相異なる。

ただし、2 つの部分文字列は、S から取り出す場所が異なれば文字列として同じでも区別して数えることに注意してください。

部分文字列とは？ S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。 例えば、AB は ABC の部分文字列ですが、AC は ABC の部分文字列ではありません。

制約

  • 1 \leq N \leq 2 \times 10^5
  • |S|=N
  • N は整数
  • S は A, B, C の 3 種類の文字のみからなる文字列

入力

入力は以下の形式で標準入力から与えられる。

N
S

出力

答えを 1 行で出力せよ。

入力例 1

6
AABBCC

出力例 1

4

S の先頭から 0 文字、末尾から 3 文字を削除すると AAB となり、これは条件を満たします。
S の先頭から 1 文字、末尾から 2 文字を削除すると ABB となり、これは条件を満たします。
S の先頭から 2 文字、末尾から 1 文字を削除すると BBC となり、これは条件を満たします。
S の先頭から 3 文字、末尾から 0 文字を削除すると BCC となり、これは条件を満たします。
また、これら以外の部分文字列は条件を満たしません。

入力例 2

6
ABCABC

出力例 2

0

どの部分文字列も条件を満たしません。

入力例 3

10
ACABCAABAB

出力例 3

17

Score : 450 points

Problem Statement

You are given a string S of length N consisting of the three characters A, B, and C.
There are \frac{N(N+1)}{2} non-empty substrings of S; find how many of them satisfy the following condition:

  • The numbers of occurrences of A, B, and C are all distinct from each other.

Count two substrings separately if they are taken from different positions in S, even if they are identical as strings.

What is a substring? A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S. For example, AB is a substring of ABC, but AC is not a substring of ABC.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • |S|=N
  • N is an integer.
  • S is a string consisting of the three characters A, B, and C.

Input

The input is given from Standard Input in the following format:

N
S

Output

Output the answer on a single line.

Sample Input 1

6
AABBCC

Sample Output 1

4

Deleting 0 characters from the beginning and 3 characters from the end of S gives AAB, which satisfies the condition.
Deleting 1 character from the beginning and 2 characters from the end of S gives ABB, which satisfies the condition.
Deleting 2 characters from the beginning and 1 character from the end of S gives BBC, which satisfies the condition.
Deleting 3 characters from the beginning and 0 characters from the end of S gives BCC, which satisfies the condition.
No other substrings satisfy the condition.

Sample Input 2

6
ABCABC

Sample Output 2

0

No substring satisfies the condition.

Sample Input 3

10
ACABCAABAB

Sample Output 3

17