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

Difficulty: HARD
Tags: String algorithms

Data structures

Range queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
str = input()
(a, b, c) = (0, 0, 0)
ans = 0
dict = {}
dict[0, 0] = 1
for i in str:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	k = (c - a, c - b)
	if k in dict:
		ans += dict[k]
		dict[k] += 1
	else:
		dict[k] = 1
print(ans)


s = input()
(a, b, c) = (0, 0, 0)
ans = 0
dict = {}
dict[0, 0] = 1
for i in s:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	k = (c - a, c - b)
	if k in dict:
		ans += dict[k]
	dict[k] = dict.get(k, 0) + 1
print(ans)


n = input()
(a, b, c) = (0, 0, 0)
f = {}
ans = 0
f[0, 0] = 1
for i in n:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	x = (c - a, c - b)
	if x in f:
		ans += f[x]
		f[x] += 1
	else:
		f[x] = 1
print(ans)


from sys import stdin
input = stdin.readline

def answer():
	(pa, pb, pc) = ([0], [0], [0])
	for i in range(n):
		pa.append(pa[-1] + (s[i] == 'A'))
		pb.append(pb[-1] + (s[i] == 'B'))
		pc.append(pc[-1] + (s[i] == 'C'))
	d = dict()
	for i in range(n + 1):
		(x, y, z) = (pa[i] - pb[i], pb[i] - pc[i], pc[i] - pa[i])
		d[x, y, z] = d.get((x, y, z), 0) + 1
	ans = 0
	for x in d.values():
		ans += x * (x - 1) // 2
	return ans
for T in range(1):
	s = input().strip()
	n = len(s)
	print(answer())


string = input()
(a, b, c) = (0, 0, 0)
substr = dict()
substr[0, 0, 0] = 1
for char in string:
	(a, b, c) = (a + (char == 'A'), b + (char == 'B'), c + (char == 'C'))
	new_sub = (a - min(a, b, c), b - min(a, b, c), c - min(a, b, c))
	if new_sub in substr:
		substr[new_sub] += 1
	else:
		substr[new_sub] = 1
solution = sum(map(lambda x: x * (x - 1) // 2, substr.values()))
print(solution)


def list_int_input():
	return [int(val) for val in input().split()]
st = input()
freq = [0, 0, 0]
mp = {}
mp[0, 0] = 1
ans = 0
for ix in range(len(st)):
	cur_ix = 0 if st[ix] == 'A' else 1 if st[ix] == 'B' else 2
	freq[cur_ix] += 1
	pair = (freq[0] - freq[1], freq[1] - freq[2])
	count = mp.get(pair, 0)
	ans += count
	mp[pair] = mp.get(pair, 0) + 1
print(ans)


from collections import defaultdict
s = '#' + input().strip()
abdiff = 0
acdiff = 0
sims = defaultdict(int)
for ch in s:
	if ch == 'A':
		abdiff += 1
		acdiff += 1
	else:
		abdiff -= ch == 'B'
		acdiff -= ch == 'C'
	sims[abdiff, acdiff] += 1
res = 0
for v in sims.values():
	res += v * (v - 1) // 2
print(res)


s = input()
(a, b, c, ans) = (0, 0, 0, 0)
d = {}
d[0, 0] = 1
for i in s:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	k = (a - b, a - c)
	if k in d:
		ans += d[k]
		d[k] += 1
	else:
		d[k] = 1
print(ans)


s = input()
dic = {(0, 0): 1}
count = 0
ac = 0
bc = 0
cc = 0
for i in range(len(s)):
	if s[i] == 'A':
		ac += 1
	elif s[i] == 'B':
		bc += 1
	else:
		cc += 1
	pair = (ac - bc, ac - cc)
	count += dic.get(pair, 0)
	dic[pair] = dic.get(pair, 0) + 1
print(count)


s = input()
from collections import defaultdict
mp = defaultdict(int)
mp[0, 0] = 1
count = 0
(a, b, c) = (0, 0, 0)
for i in s:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	else:
		c += 1
	m = (a - b, a - c)
	count += mp[m]
	mp[m] += 1
print(count)


s = input()
dict = {}
a = 0
b = 0
c = 0
ans = 0
dict[0, 0, 0] = 1
for i in range(0, len(s)):
	if s[i] == 'A':
		a += 1
	if s[i] == 'B':
		b += 1
	if s[i] == 'C':
		c += 1
	mi = min(a, min(b, c))
	if (a - mi, b - mi, c - mi) in dict.keys():
		ans += dict[a - mi, b - mi, c - mi]
		dict[a - mi, b - mi, c - mi] += 1
	else:
		dict[a - mi, b - mi, c - mi] = 1
print(ans)


string = list(input())
ma = {}
ma[0, 0, 0] = 1
a = 0
b = 0
c = 0
cnt = 0
for i in range(len(string)):
	if string[i] == 'A':
		a += 1
	if string[i] == 'B':
		b += 1
	if string[i] == 'C':
		c += 1
	mi = min(a, b, c)
	if (a - mi, b - mi, c - mi) in ma.keys():
		cnt += ma[a - mi, b - mi, c - mi]
		ma[a - mi, b - mi, c - mi] += 1
	else:
		ma[a - mi, b - mi, c - mi] = 1
print(cnt)


s = input()
d = {}
(a, b, c) = (0, 0, 0)
d[0, 0, 0] = 1
count = 0
for i in range(len(s)):
	if s[i] == 'A':
		a += 1
	if s[i] == 'B':
		b += 1
	if s[i] == 'C':
		c += 1
	mi = min(a, b, c)
	if (a - mi, b - mi, c - mi) in d.keys():
		count += d[a - mi, b - mi, c - mi]
		d[a - mi, b - mi, c - mi] += 1
	else:
		d[a - mi, b - mi, c - mi] = 1
print(count)


st = input()
d = {}
d[0, 0] = 1
a = b = c = 0
res = 0
for i in st:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	val = (a - b, a - c)
	if val in d:
		res += d[val]
	d[val] = d.get(val, 0) + 1
print(res)


from sys import stdin
from collections import defaultdict
s = stdin.readline()
d = {}
d[0, 0] = 1
cnt = {}
cnt['A'] = cnt['B'] = cnt['C'] = 0
res = 0
for c in s[:-1]:
	cnt[c] += 1
	dif = (cnt['B'] - cnt['A'], cnt['C'] - cnt['A'])
	if dif in d:
		res += d[dif]
		d[dif] += 1
	else:
		d[dif] = 1
print(res)


s = input().strip()
from collections import defaultdict
seen = defaultdict(int)
ans = 0
prev = [0, 0]
seen[0, 0] = 1
for (i, elem) in enumerate(s):
	if elem == 'A':
		prev[0] += 1
		prev[1] += 1
	elif elem == 'B':
		prev[0] -= 1
	else:
		prev[1] -= 1
	ans += seen[prev[0], prev[1]]
	seen[prev[0], prev[1]] += 1
print(ans)


n = input()
a = b = c = 0
d = {}
d[0, 0] = 1
k = 0
for i in n:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	m = (a - b, a - c)
	if m in d:
		k += d[m]
		d[m] += 1
	else:
		d[m] = 1
print(k)


try:
	s = input()
	d = {(0, 0): 1}
	(a, b, c, r) = (0, 0, 0, 0)
	for i in s:
		if i == 'A':
			a += 1
		elif i == 'B':
			b += 1
		else:
			c += 1
		t = (c - a, c - b)
		if t in d:
			r += d[t]
			d[t] += 1
		else:
			d[t] = 1
	print(r)
except:
	pass


s = input()

def fun(s):
	i = 0
	j = 1
	c = 0
	mp = {}
	mp[0, 0] = 1
	a = 0
	b = 0
	c = 0
	t = 0
	res = 0
	for i in s:
		if i == 'A':
			a += 1
		elif i == 'B':
			b += 1
		else:
			c += 1
		t = (c - a, c - b)
		if t not in mp:
			res += 0
		else:
			res += mp[t]
		if t not in mp:
			mp[t] = 1
		else:
			mp[t] += 1
	return res
print(fun(s))


z = input()
(a, b, c) = (0, 0, 0)
res = 0
dict = {}
dict[0, 0] = 1
for i in z:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	k = (c - a, c - b)
	if k in dict:
		res += dict[k]
	dict[k] = dict.get(k, 0) + 1
print(res)


from math import ceil, sqrt, log, gcd
from collections import deque, defaultdict as dd
from os import path
import sys
try:
	str = input()
	dictk = {(0, 0): 1}
	(a, b, c, res) = (0, 0, 0, 0)
	for s in str:
		if s == 'A':
			a += 1
		elif s == 'B':
			b += 1
		else:
			c += 1
		t = (c - a, c - b)
		if t in dictk:
			res += dictk[t]
			dictk[t] += 1
		else:
			dictk[t] = 1
	print(res)
except:
	pass


p = input()

def fun(p):
	i = 0
	j = 1
	c = 0
	m = {}
	m[0, 0] = 1
	(a, b, c, t) = (0, 0, 0, 0)
	res = 0
	for i in p:
		if i == 'A':
			a += 1
		elif i == 'B':
			b += 1
		else:
			c += 1
		t = (c - a, c - b)
		if t not in m:
			res += 0
		else:
			res += m[t]
		if t not in m:
			m[t] = 1
		else:
			m[t] += 1
	return res
print(fun(p))


def dostuff(s):
	d = {'0,0': 1}
	ans = 0
	ta = 0
	tb = 0
	tc = 0
	for i in range(len(s)):
		t = s[i]
		if t == 'A':
			ta += 1
		if t == 'B':
			tb += 1
		if t == 'C':
			tc += 1
		k = str(ta - tb) + ',' + str(ta - tc)
		if k in d:
			ans += d[k]
			d[k] += 1
		else:
			d[k] = 1
	print(ans)
s = input()
dostuff(s)


s = input()
(a, b, c) = (0, 0, 0)
res = 0
f = {}
f[0, 0] = 1
for i in s:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	x = (c - a, c - b)
	if x in f:
		res += f[x]
		f[x] += 1
	else:
		f[x] = 1
print(res)


s = input()
kfreq = {(0, 0): 1}
ai = bi = ci = 0
for ch in s:
	if ch == 'A':
		ai += 1
	elif ch == 'B':
		bi += 1
	elif ch == 'C':
		ci += 1
	ki = (ai - bi, ai - ci)
	if ki in kfreq:
		kfreq[ki] += 1
	else:
		kfreq[ki] = 1
ways = 0
for freq in kfreq.values():
	kfc2 = freq * (freq - 1) // 2
	ways += kfc2
print(ways)


s = list(input())
l = len(s)
a = [0] * (l + 1)
b = [0] * (l + 1)
c = [0] * (l + 1)
d = {}
counta = 0
countb = 0
countc = 0
for i in range(l):
	if s[i] == 'A':
		counta += 1
	elif s[i] == 'B':
		countb += 1
	else:
		countc += 1
	a[i + 1] = counta
	b[i + 1] = countb
	c[i + 1] = countc
ans = 0
for i in range(l + 1):
	d[a[i] - b[i], a[i] - c[i]] = d.get((a[i] - b[i], a[i] - c[i]), 0) + 1
	ans += d[a[i] - b[i], a[i] - c[i]] - 1
print(ans)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')
from sys import maxsize

def solve():
	s = get_string()
	n = len(s)
	d = dict()
	d[0, 0] = 1
	(a, b, c) = (0, 0, 0)
	ans = 0
	for i in range(n):
		if s[i] == 'A':
			a += 1
		elif s[i] == 'B':
			b += 1
		else:
			c += 1
		other = (a - b, a - c)
		if other in d:
			ans += d[other]
			d[other] += 1
		else:
			d[other] = 1
	get_print_int(ans)
solve()


s = input()
n = len(s)
count_A = [0] * n
count_B = [0] * n
count_C = [0] * n
for i in range(n):
	if s[i] == 'A':
		count_A[i] += 1
	elif s[i] == 'B':
		count_B[i] += 1
	else:
		count_C[i] += 1
for i in range(1, n):
	(a, b, c) = (count_A[i] + count_A[i - 1], count_B[i] + count_B[i - 1], count_C[i] + count_C[i - 1])
	x = min(a, b, c)
	(count_A[i], count_B[i], count_C[i]) = (a - x, b - x, c - x)
counts = {}
counts[0, 0, 0] = 1
for i in range(n):
	key = (count_A[i], count_B[i], count_C[i])
	counts[key] = counts.get(key, 0) + 1
ans = 0
for v in counts.values():
	if v:
		ans += v * (v - 1) // 2
print(ans)


try:
	string = input()
	dictk = {(0, 0): 1}
	a = 0
	b = 0
	c = 0
	res = 0
	for s in string:
		if s == 'A':
			a += 1
		elif s == 'B':
			b += 1
		else:
			c += 1
		t = (c - a, c - b)
		if t in dictk:
			res += dictk[t]
			dictk[t] += 1
		else:
			dictk[t] = 1
	print(res)
except:
	pass


s = input()
from collections import defaultdict
m = defaultdict(int)
m[0, 0] = 1
ans = 0
(a, b, c) = (0, 0, 0)
for i in s:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	else:
		c += 1
	k = (a - b, a - c)
	ans += m[k]
	m[k] += 1
print(ans)


s = '#' + input().strip()
n = len(s)
d = {}
sm = 0
a = 0
b = 0
c = 0
for i in range(n):
	if s[i] == 'A':
		a += 1
	if s[i] == 'B':
		b += 1
	if s[i] == 'C':
		c += 1
	sm += d.get((a - b, a - c), 0)
	d[a - b, a - c] = d.get((a - b, a - c), 0) + 1
print(sm)


from collections import defaultdict
s = input().strip()
ls = len(s)
ca = 0
cb = 0
cc = 0
c = [[ca, cb, cc]]
for i in s:
	if i == 'A':
		ca += 1
	if i == 'B':
		cb += 1
	if i == 'C':
		cc += 1
	c.append([ca, cb, cc])
g = defaultdict(int)
for i in range(ls + 1):
	mini = min(c[i])
	c[i] = [j - mini for j in c[i]]
	g[tuple(c[i])] += 1
ans = 0
for i in g:
	temp = g[i]
	if temp > 1:
		ans += temp * (temp - 1) // 2
print(ans)


s = input()
dicti = {}
dicti[0, 0] = 1
a = b = c = 0
res = 0
for i in s:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	elif i == 'C':
		c += 1
	ans = (a - b, a - c)
	if ans in dicti:
		res += dicti[ans]
	dicti[ans] = dicti.get(ans, 0) + 1
print(res)


t = list(input())
count = 0
k = {}
k[0, 0, 0] = 1
a = 0
b = 0
c = 0
for i in range(len(t)):
	if t[i] == 'A':
		a += 1
	elif t[i] == 'B':
		b += 1
	elif t[i] == 'C':
		c += 1
	mi = min(a, b, c)
	if (a - mi, b - mi, c - mi) in k.keys():
		count += k[a - mi, b - mi, c - mi]
		k[a - mi, b - mi, c - mi] += 1
	else:
		k[a - mi, b - mi, c - mi] = 1
print(count)


x = str(input())
dic = {(0, 0): 1}
a = b = c = 0
ans = 0
for i in x:
	if i == 'A':
		a += 1
	elif i == 'B':
		b += 1
	else:
		c += 1
	if (a - b, a - c) not in dic:
		dic[a - b, a - c] = 1
	else:
		dic[a - b, a - c] += 1
for i in dic.values():
	ans += i * (i - 1) // 2
print(ans)


import sys
from collections import Counter
import numpy as np
import math
test = False
answer = 0
prev = {}
current_count = [0, 0, 0]
prev[tuple(current_count)] = 1
S = input().strip()
for letter in S:
	if letter == 'A':
		current_count = [current_count[0] + 1, current_count[1] + 1, current_count[2]]
	elif letter == 'B':
		current_count = [current_count[0] - 1, current_count[1], current_count[2] + 1]
	else:
		current_count = [current_count[0], current_count[1] - 1, current_count[2] - 1]
	current_count = tuple(current_count)
	if current_count in prev:
		answer += prev[current_count]
		prev[current_count] += 1
		if test:
			print(current_count)
	else:
		prev[current_count] = 1
print(answer)
if test:
	print(' ')


s = input()
count = 0
map = {}
map[0, 0] = 1
(A, B, C) = (0, 0, 0)
ans = 0
for i in s:
	if i == 'A':
		A += 1
	elif i == 'B':
		B += 1
	elif i == 'C':
		C += 1
	temp = (C - A, C - B)
	if temp in map:
		ans += map[temp]
		map[temp] += 1
	else:
		map[temp] = 1
print(ans)


from os import path
import sys
try:
	strr = input()
	d = {(0, 0): 1}
	(a, b, c, count) = (0, 0, 0, 0)
	for s in strr:
		if s == 'A':
			a += 1
		elif s == 'B':
			b += 1
		else:
			c += 1
		t = (c - a, c - b)
		if t in d:
			count += d[t]
			d[t] += 1
		else:
			d[t] = 1
	print(count)
except:
	pass