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
/* -----------------------
Autor: Tomasz Boguslawski
-------------------------- */
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<iomanip>
#include<string>
#include<sstream>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include <fstream>
#include<math.h>

#define LL long long
#define FOR(x, b, e) for(LL x = b; x <= (e); x++)
#define FORD(x, b, e) for(LL x = b; x >= (e); x--)
#define VAR(v, n) __typeof(n) v = (n)
#define ALL(c) (c).begin(), (c).end()
#define FOREACH(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define DEBUG if (debug)
#define MIN(a,b) ((a>b)?b:a)
#define MAX(a,b) ((a>b)?a:b)

using namespace std;
string slowo;

// zlicza "jednoliterkowce", czyli zbalansowane podslowa skladajace sie z samych literek a lub samych b lub samych c
LL zlicz_1lit()
{
    LL b=0;
    char c='#';
    LL total=0;
    FOR(i,0,slowo.length()-1)
    {
        if (slowo[i]==c) b++;
        else
        {
            total = total + (b*(b+1))/2;
            b=1; c=slowo[i];
        }
    }
    total = total + (b*(b+1))/2;
    return total;
}

// zlicza "dwuliterkowce", czyli zbalansowane podslowa skladajace sie z samych literek c1 i c2
LL zlicz_2lit(char c1, char c2)
{
    map<int, int> m; // ile dodac liter c1, zeby zbalansowac
    LL dodawajnik = 0;
    LL total=0;
    FOR(i,0,slowo.length()-1)
    {
        if (slowo[i]==c1) { dodawajnik--; m[-1-dodawajnik]++; total+=m[-dodawajnik]; }
        else if (slowo[i]==c2) { dodawajnik++; m[1-dodawajnik]++; total+=m[-dodawajnik]; }
        else { m.clear(); dodawajnik=0; }
    }
    return total;
}

map<LL,LL> mm;

void increment_at(LL a, LL b)
{
    a+=1048576; b+=1048576;
    mm[(a<<20)+b]++;
}

LL get(LL a, LL b)
{
    a+=1048576; b+=1048576;
    return mm[(a<<20)+b];
}

// zlicza "trzyliterkowce", czyli zbalansowane podslowa skladajace sie z literek a, b i c.
LL zlicz_3lit()
{
    mm.clear();
    LL dodawajnik_a=0; LL dodawajnik_b=0;
    LL total=0;
    FOR(i,0,slowo.length()-1)
    {
        if (slowo[i]=='a') { dodawajnik_a--; increment_at(-1-dodawajnik_a, 0-dodawajnik_b); }
        else if (slowo[i]=='b') { dodawajnik_b--; increment_at(0-dodawajnik_a, -1-dodawajnik_b); }
        else { dodawajnik_a++; dodawajnik_b++; increment_at(1-dodawajnik_a, 1-dodawajnik_b); }
        total+=get(-dodawajnik_a, -dodawajnik_b);
    }
    return total;
}

LL zlicz()
{
    LL total=zlicz_1lit();
    total+=zlicz_2lit('a','b');
    total+=zlicz_2lit('a','c');
    total+=zlicz_2lit('b','c');
    total+=zlicz_3lit();
    return total;
}

/// MAIN
int main(int argc, char* argv[])
{
    // magic formula, which makes streams work faster:
	ios_base::sync_with_stdio(0);

    cin >> slowo;
    cout << zlicz() << '\n';

    return 0;
};