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'.
The first line of the input contains an ABC-string S.
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.
1 ≤ |S| ≤ 1 000 000; where |S| denotes the length of the given ABC-string.
Input: ABACABA Output: 2
In the example you should count S[2..4] = "BAC" and S[4..6] = "CAB".
|Tags||ad-hoc, cook44, kostya_by, map, simple|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.5, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.