ABC-Strings  Problem code: ABCSTR

SUBMIT MY SUBMISSIONS ALL SUBMISSIONS

All submissions for this problem are available.

Read problems statements in Mandarin Chinese and Russian as well.

Mike likes strings. He is also interested in algorithms. A few days ago he discovered for himself a very nice problem:

You are given an AB-string S. You need to count the number of substrings of S, which have an equal number of 'A'-s and 'B'-s.

Do you know how to solve it? Good. Mike will make the problem a little bit more difficult for you.

You are given an ABC-string S. You need to count the number of substrings of S, which have an equal number of 'A'-s, 'B'-s and 'C'-s.

A string is called AB-string if it doesn't contain any symbols except 'A' or 'B'. A string is called ABC-string if it doesn't contain any symbols except 'A', 'B' or 'C'.

Input

The first line of the input contains an ABC-string S.

Output

Your output should contain the only integer, denoting the number of substrings of S, which have an equal number of 'A'-s, 'B'-s and 'C'-s.

The answer can go above a 32-bit integer. Please, use 64-bit integers for storing and processing data.

Constraints

1 ≤ |S| ≤ 1 000 000; where |S| denotes the length of the given ABC-string.

Example

Input:
ABACABA

Output:
2

Explanation

In the example you should count S[2..4] = "BAC" and S[4..6] = "CAB".

EXPLANATION:

Let,
A_i = Number of ‘A’s in S between the indexes 1 and i (inclusive).
B_i = Number of ‘B’s in S between the indexes 1 and i (inclusive).
C_i = Number of ‘C’s in S between the indexes 1 and i (inclusive).

Let’s consider the substring S_j...i :
Number of ‘A’-s in that substring = A_i - A_j-1
Number of ‘B’-s in that substring = B_i - B_j-1
Number of ‘C’-s in that substring = C_i - C_j-1

So for that substring to be good: A_i - A_j-1 = B_i - B_j-1 = C_i - C_j-1

Alternatively the following two conditions are enough for that substring to be good:

A_i - B_i = A_j-1 - B_j-1
A_i - C_i = A_j-1 - C_j-1

Go from left to right and for each index i find the number of valid good substrings which ends at i. The number of such substrings would be the number of indexes k (k < i) where (A_i - B_i, A_i - C_i )= (A_k - B_k, A_k - C_k ). That can be obtained if the pair (A_k - B_k, A_k - C_k )for all k are stored in a key-value storage where the key being the pair and value being the number indexes having that difference pair. If using C++, STL Map can be used. The author did not use a map, instead he computed all the difference pairs and then sorted those and then find the number of equal pairs.

Here , we use a map implementation of the above code where we update (a-b b-c) pair for every occurence of a ,b,c ; Now suppose we have a value at a certain index i = (a,b,c) now we add number of pairs having the value (a-b ,b-c)  given by map(a-b ,b-c) and add it to answer then update map(a-b , b-c).

           ****** code code code code*******

#include<iostream>

#include<stdio.h>

#include<string.h>

#include<map>

#define mp make_pair

using namespace std;

char str[1000010];

int main()

{

cin>>str;

int l=strlen(str);

map<pair<int,int>  ,int> pairs;

int a=0;

int b=0;

int c=0;

long long int ans=0;

pairs[make_pair(0,0)]++;

for(int i=0;i<l;i++)

{

if(str[i]=='A')

{

a++;

}

if(str[i]=='B')

{

b++;

}

if(str[i]=='C')

c++;

ans += pairs[mp(a - b, c - b)];

        pairs[mp(a - b, c - b)]++;

}

cout<<ans<<endl;

return 0;

}