#include <iostream> #include <string> #include <map> #include <tuple> using namespace std; int main() { string word; cin >> word; int N = word.length(); int a = 0, b = 0, c = 0; int act = 0; int zba = 0; char last = 'd'; char character; map<tuple<int, int>, int> abc; map<int, int> ab; map<int, int> ac; map<int, int> bc; abc[make_tuple(0, 0)] = 1; ab[0] = 1; ac[0] = 1; bc[0] = 1; for (int i = 0; i < N; i++) { character = word.at(i); if (character == 'a') { a++; for (auto const &key : bc) zba += key.second * (key.second - 1)/2; bc.erase(bc.begin(), bc.end()); bc[0] = 1; ab[a-b]++; ac[a-c]++; } else if (character == 'b') { b++; for (auto const &key : ac) zba += key.second * (key.second - 1)/2; ac.erase(ac.begin(), ac.end()); ac[0] = 1; ab[a-b]++; bc[b-c]++; } else { c++; for (auto const &key : ab) zba += key.second * (key.second - 1)/2; ab.erase(ab.begin(), ab.end()); ab[0] = 1; ac[a-c]++; bc[b-c]++; } if (character == last) { act++; } else { zba += (act + 1)*act/2; act = 1; last = character; } abc[make_tuple(a-b, a-c)]++; } if (act != 1) zba += (act + 1)*act/2; for (auto const &key : ab) zba += key.second * (key.second - 1)/2; for (auto const &key : ac) zba += key.second * (key.second - 1)/2; for (auto const &key : bc) zba += key.second * (key.second - 1)/2; for (auto const &i : abc) zba += i.second * (i.second - 1)/2; cout << zba << endl; return 0; }
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 | #include <iostream> #include <string> #include <map> #include <tuple> using namespace std; int main() { string word; cin >> word; int N = word.length(); int a = 0, b = 0, c = 0; int act = 0; int zba = 0; char last = 'd'; char character; map<tuple<int, int>, int> abc; map<int, int> ab; map<int, int> ac; map<int, int> bc; abc[make_tuple(0, 0)] = 1; ab[0] = 1; ac[0] = 1; bc[0] = 1; for (int i = 0; i < N; i++) { character = word.at(i); if (character == 'a') { a++; for (auto const &key : bc) zba += key.second * (key.second - 1)/2; bc.erase(bc.begin(), bc.end()); bc[0] = 1; ab[a-b]++; ac[a-c]++; } else if (character == 'b') { b++; for (auto const &key : ac) zba += key.second * (key.second - 1)/2; ac.erase(ac.begin(), ac.end()); ac[0] = 1; ab[a-b]++; bc[b-c]++; } else { c++; for (auto const &key : ab) zba += key.second * (key.second - 1)/2; ab.erase(ab.begin(), ab.end()); ab[0] = 1; ac[a-c]++; bc[b-c]++; } if (character == last) { act++; } else { zba += (act + 1)*act/2; act = 1; last = character; } abc[make_tuple(a-b, a-c)]++; } if (act != 1) zba += (act + 1)*act/2; for (auto const &key : ab) zba += key.second * (key.second - 1)/2; for (auto const &key : ac) zba += key.second * (key.second - 1)/2; for (auto const &key : bc) zba += key.second * (key.second - 1)/2; for (auto const &i : abc) zba += i.second * (i.second - 1)/2; cout << zba << endl; return 0; } |