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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
// Jan Burdzicki
#include <bits/stdc++.h>
using namespace std;

const int DLUGOSC_ALFABETU = 3;

struct Stan
{
	int roznica_1, roznica_2;

	bool operator < (const Stan& inny) const
	{
		if(roznica_1 != inny.roznica_1)
		{
			return roznica_1 < inny.roznica_1;
		}

		else
		{
			return roznica_2 < inny.roznica_2;
		}
	}
};

// Liczymy ilosc podslow zawierajacych taka sama ilosc 1 literki
void policz_ilosc_podslow_zawierajacych_taka_sama_ilosc_1_literki(string& s, int rozmiar, long long& wynik)
{
	char poprzednia_literka = 'a';

	int ilosc = 0;

	for(int i = 0; i < rozmiar; i++)
	{
		if(s[i] != poprzednia_literka)
		{
			poprzednia_literka = s[i];

			ilosc = 0;
		}

		ilosc++;

		wynik += ilosc;
	}
}

// Liczymy ilosc podslow zawierajacych taka sama ilosc 2 literek
void policz_ilosc_podslow_zawierajacych_taka_sama_ilosc_2_literek(string& s, int rozmiar, long long& wynik)
{
	vector <int> permutacja = {0, 0, 1};

	do
	{
		int indeks_min;

		for(int i = 0; i < DLUGOSC_ALFABETU; i++)
		{
			if(permutacja[i] != 1)
			{
				indeks_min = i;
			}
		}

		map <int, long long> mapka;

		mapka[0] = 1;

		int ilosc = 0;

		for(int i = 0; i < rozmiar; i++)
		{
			int indeks = s[i] - 'a';

			if(permutacja[indeks] == 1)
			{
				ilosc = 0;

				mapka.clear();

				mapka[0] = 1;

				continue;
			}

			if(indeks == indeks_min)
			{
				ilosc++;
			}

			else
			{
				ilosc--;
			}

			wynik += mapka[ilosc];

			mapka[ilosc]++;
		}

	} while(next_permutation(permutacja.begin(), permutacja.end()));
}

// Liczymy ilosc podslow zawierajacych taka sama ilosc 3 literek
void policz_ilosc_podslow_zawierajacych_taka_sama_ilosc_3_literek(string& s, int rozmiar, long long& wynik)
{
	vector <int> ilosci(DLUGOSC_ALFABETU);

	map <Stan, long long> mapka;

	mapka[{0, 0}] = 1;

	for(int i = 0; i < rozmiar; i++)
	{
		int indeks = s[i] - 'a';

		ilosci[indeks]++;

		int roznica_1 = ilosci[0] - ilosci[1];
		int roznica_2 = ilosci[0] - ilosci[2];

		Stan stan = {roznica_1, roznica_2};

		wynik += mapka[stan];

		mapka[stan]++;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	string s;
	cin >> s;

	// Program mozna jeszcze zoptymalizowac

	int rozmiar = (int) s.size();

	long long wynik = 0;

	policz_ilosc_podslow_zawierajacych_taka_sama_ilosc_1_literki(s, rozmiar, wynik);
	policz_ilosc_podslow_zawierajacych_taka_sama_ilosc_2_literek(s, rozmiar, wynik);
	policz_ilosc_podslow_zawierajacych_taka_sama_ilosc_3_literek(s, rozmiar, wynik);

	cout << wynik << "\n";
	return 0;
}