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
/*
	Zadanie: Zbalansowane słowa
	Autor: Tomasz Kwiatkowski
*/

#include <bits/stdc++.h>

#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;

ll cnt(string& s, vector<int> weight, vector<int> weight2 = {0, 0, 0})
{
	map<pair<ll, ll>, int> prv;
	ll pref = 0, pref2 = 0;
	ll ans = 0;
	for (auto c : s) {
		++prv[{pref, pref2}];
		pref += weight[c - 'a'];
		pref2 += weight2[c - 'a'];
		ans += prv[{pref, pref2}];
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0);
	
	string s;
	cin >> s;
	int n = s.size();

	ll ans = 0;
	ans += cnt(s, {0, 1, 1}); // {a}
	ans += cnt(s, {1, 0, 1}); // {b}
	ans += cnt(s, {1, 1, 0}); // {c}
	ans += cnt(s, {-1, 1, n+1}); // {a, b}
	ans += cnt(s, {-1, n+1, 1}); // {a, c}
	ans += cnt(s, {n+1, -1, 1}); // {b, c}
	ans += cnt(s, {1, 1, -2}, {1, -1, 0}) ;// {a, b, c}

	cout << ans << '\n';
	return 0;
}