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
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
#pragma GCC target("sse,sse2,sse3,mmx,abm,tune=native")
typedef long long lld;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
#define For(i,s,a) for(int i = (int)s; i < (int)a; ++i)
#define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it)
#define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it)
#define sz size()
#define pb push_back
#define eb emplace_back
#define ff first
#define dd second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define make_unique(x) (x).erase( unique(all(x)), (x).end())
#define popcnt(x) __builtin_popcount(x)

//using namespace std::chrono;
//#define time_since duration_cast<nanoseconds>(system_clock::now().time_since_epoch())

template<typename Ta, typename Tb>
ostream & operator <<(ostream & os, pair<Ta, Tb> x){
	return os << x.ff << " " << x.dd;
}

char s[300001];
map<int, int>duo;
using tri = tuple<int, int, int>;
map<tri, int>triple;
int ile[3], prv[3], tmp[3];

lld tr(lld x) {return x * (x - 1) / 2ll;}

int32_t main() {
	scanf("%s", s);
	int n = strlen(s);
	prv[s[0] == 'c' ? 2 : 0] = -1;
	prv[1] = -2;
	prv[s[0] == 'c' ? 0 : 2] = -3;
	tmp[0] = tmp[1] = tmp[2] = 0;
	triple[tie(tmp[0], tmp[1], tmp[2])] = 1;
	lld wyn = 0, cont = 0, diff = 0;
	duo[0] = 1;
	For(i, 0, n) {
		if(!i || s[i] != s[i - 1])
			cont = 1;
		else
			++cont;
		wyn += cont;
		switch(s[i]) {
			case 'a':
				++tmp[0];
				++tmp[1];
				break;
			case 'b':
				++tmp[2];
				--tmp[0];
				break;
			case 'c':
				--tmp[1];
				--tmp[2];
				break;
		}
		triple[tie(tmp[0], tmp[1], tmp[2])]++;
		wyn += triple[tie(tmp[0], tmp[1], tmp[2])] - 1;
		
		int pr = prv[s[i] - 'a'];
		int maxx = max(prv[0], max(prv[1], prv[2]));
		int minx = min(prv[0], min(prv[1], prv[2]));
		
		++ile[s[i] - 'a'];
		if(pr == minx) {
			duo.clear();
			duo[0] = 1;
			For(j, 0, 3)
				ile[j] = 0;
			for(int j = i - 1; j >= 0 && prv[s[j] - 'a'] == maxx; --j) {
				++ile[s[j] - 'a'];
				++duo[s[j] > s[i] ? -ile[s[j] - 'a'] : ile[s[j] - 'a']];
			}
			if(s[i] - 'a' == 0)
				diff = 1 - ile[s[i - 1] - 'a'];
			else if(s[i] - 'a' == 2)
				diff = ile[s[i - 1] - 'a'] - 1;
			else diff = (ile[s[i - 1] - 'a'] - 1) * (maxx == prv[0] ? 1 : -1);
		} else {
			if(s[i] - 'a' == 0) {
				++diff;
			} else if(s[i] - 'a' == 2) {
				--diff;
			} else diff += min(prv[0], min(prv[1], prv[2])) == prv[2] ? -1 : 1;
		}
		duo[diff]++;
		wyn += duo[diff] - 1;
		//cout << diff << " " << duo[diff] << " " << ile[0] << " " << ile[1] << " " << ile[2] << " " << duo[diff] - 1 << endl;
		prv[s[i] - 'a'] = i;
	}
	printf("%lld\n", wyn);
}