1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define ll long long

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	string s;
	cin >> s;
	int n = (int)s.size();
	map <pair <int, int>, int> abc;
	vector <pair <int, int> > ab(2 * n + 1), bc(2 * n + 1), ca(2 * n + 1);
	for (int i = 0; i < ab.size(); i++)
		ab[i] = make_pair(-1, -1);
	for (int i = 0; i < bc.size(); i++)
		bc[i] = make_pair(-1, -1);
	for (int i = 0; i < ca.size(); i++)
		ca[i] = make_pair(-1, -1);
	ab[n] = bc[n] = ca[n] = make_pair(0, 0);
	vector <ll> dpabc(n + 1), dpab(n + 1), dpbc(n + 1), dpca(n + 1);
	abc[make_pair(0, 0)] = 1;
	ll res = 0;
	int a = 0, b = 0, c = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == 'a') 
			a++;
		else if (s[i] == 'b')
			b++;
		else
			c++;

		pair <int, int> para = make_pair(a - b, b - c);
		if (abc.find(para) != abc.end())
			dpabc[i + 1] = 1 + dpabc[abc[para]];
		abc[para] = i + 1;
	
		if (ab[a - b + n].ff == c && a > 0 && b > 0)
			dpab[i + 1] = 1 + dpab[ab[a - b + n].ss];
		ab[a - b + n] = make_pair(c, i + 1);

		if (bc[b - c + n].ff == a && b > 0 && c > 0)
			dpbc[i + 1] = 1 + dpbc[bc[b - c + n].ss];
		bc[b - c + n] = make_pair(a, i + 1);

		if (ca[c - a + n].ff == b && c > 0 && a > 0)
			dpca[i + 1] = 1 + dpca[ca[c - a + n].ss];
		ca[c - a + n] = make_pair(b, i + 1);
		
		//cout << i + 1 << ": " << dpabc[i+1] << " " << dpab[i+1] << " " << dpbc[i+1] << " " << dpca[i+1] << "\n";
		res += dpabc[i+1] + dpab[i+1] + dpbc[i+1] + dpca[i+1];
	}
	char q = 'd';
	int ile = 0;
	for (int i = 0; i < n; i++) {
		if (q != s[i]) {
			q = s[i];
			ile = 0;
		}
		ile++;
		res += ile;
	}
	cout << res << "\n";
	return 0;
}