E - A > B substring 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

A, B, C の 3 種類の文字からなる長さ N の文字列 S が与えられます。

S の空でない連続する部分文字列は \dfrac{N(N+1)}2 個ありますが、そのうち A が B よりも多く含まれるものはいくつあるか求めてください。

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

部分文字列とは

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

制約

  • 1\le N\le5\times10 ^ 5
  • S は A, B, C からなる長さ N の文字列
  • N は整数

入力

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

N
S

出力

S の連続する部分文字列のうち A が B よりも多く含まれるものの個数を出力せよ。

入力例 1

10
ACBBCABCAB

出力例 1

8

以下の 8 つの部分文字列が条件を満たします。

  • A：S の 1 文字目から 1 文字目
  • AC：S の 1 文字目から 2 文字目
  • CA：S の 5 文字目から 6 文字目
  • CABCA：S の 5 文字目から 9 文字目
  • A：S の 6 文字目から 6 文字目
  • ABCA：S の 6 文字目から 9 文字目
  • CA：S の 8 文字目から 9 文字目
  • A：S の 9 文字目から 9 文字目

これら以外の部分文字列は条件を満たさないため、8 を出力してください。

A や CA は複数箇所から取り出すことができますが、取り出す場所が異なれば区別して数えることに注意してください。

入力例 2

4
CCBC

出力例 2

0

条件を満たす部分文字列が存在しないこともあります。

入力例 3

36
CABACBBBBBAABABACCBCABCCABAABABBCBAC

出力例 3

136

Score : 450 points

Problem Statement

You are given a string S of length N consisting of three kinds of characters: A, B, and C.

There are \dfrac{N(N+1)}2 non-empty contiguous substrings of S. Find how many of them contain more As than Bs.

Note that two substrings are counted separately if they are taken from different positions in S, even if they are equal 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\le N\le5\times10 ^ 5
  • S is a string of length N consisting of A, B, and C.
  • N is an integer.

Input

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

N
S

Output

Print the number of contiguous substrings of S that contain more As than Bs.

Sample Input 1

10
ACBBCABCAB

Sample Output 1

8

The following eight substrings satisfy the condition:

  • A: 1st to 1st character of S
  • AC: 1st to 2nd character of S
  • CA: 5th to 6th character of S
  • CABCA: 5th to 9th character of S
  • A: 6th to 6th character of S
  • ABCA: 6th to 9th character of S
  • CA: 8th to 9th character of S
  • A: 9th to 9th character of S

All other substrings do not satisfy the condition, so print 8.

Note that A and CA can be taken from multiple positions, but they are counted separately if taken from different positions.

Sample Input 2

4
CCBC

Sample Output 2

0

There may be no substrings that satisfy the condition.

Sample Input 3

36
CABACBBBBBAABABACCBCABCCABAABABBCBAC

Sample Output 3

136