ABC-Strings | CodeChef

ABC-Strings

Problem code: ABCSTR

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".

Author: 6★kostya_by
Tester: 6★gerald
Editorial http://discuss.codechef.com/problems/ABCSTR
Tags ad-hoc, cook44, kostya_by, map, simple
Date Added: 8-02-2014
Time Limit: 2 sec
Source Limit: 50000 Bytes
Languages: C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS


Comments

  • Please login at the top to post a comment.

SUCCESSFUL SUBMISSIONS


Fetching successful submissions