Beautiful Strings

3.4

14 votes
Ad-Hoc, Algorithms, Approved, Medium, Open, Sorting
Problem

A string is beautiful if it has equal number of a,b,and c in it.
Example "abc" , "aabbcc" , "dabc" , "" are beautiful.
Given a string of alphabets containing only lowercas aplhabets (a-z), output the number of non-empty beautiful substring of the given string.

Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Each test case consists of a line containing a string a length L.

Output
For each test case, output a single line containing the number of beautiful substring.

Constraints
1<=T<=10
1<=L<=100000

Sample Input
2
abacbcba
dbacd
Sample Output
5
6
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

Test Case 1 The output will be 5 ("abacbc","bac",”acb”, ”acbcba”,"cba") Test Case 2 The output will be 6 ("d", "dbac", "dbacd", ”bac”, "bacd", "d")

Editor Image

?