#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define SIZE(a) ((int)a.size()) ll compute_single(string &s, char a) { ll res = 0; int len = 0; for(char c : s) { if(c == a) { len++; } else { len=0; } res+=len; } return res; } ll compute_pairs(string &s, char a, char b) { map<int, int> m; m[0] = 0; int diff = 0; ll res = 0; vector<int> dp(SIZE(s)+1); for(int i=0; i < SIZE(s); i++) { char c = s[i]; if(c == a || c == b) { if(c == a) { diff++; } else { diff--; } if(m.count(diff)) { dp[i+1] = dp[m[diff]]+1; } m[diff] = i+1; res+=dp[i+1]; } else { diff = 0; m.clear(); m[0] = 0; } } return res; } ll compute_triples(string &s) { map<pii, int> m; int diff1=0, diff2=0; ll res = 0; vector<int> dp(SIZE(s)+1); m[{0, 0}] = 0; for(int i=0; i < SIZE(s); i++) { char c = s[i]; if(c == 'a') { diff1++; diff2++; } else if(c == 'b') { diff1--; } else { diff2--; } if(m.count({diff1, diff2})) { dp[i+1] = dp[m[{diff1, diff2}]]+1; } m[{diff1, diff2}] = i+1; res+=dp[i+1]; } return res; } int main() { ios_base::sync_with_stdio(0); string s; cin >> s; ll res = compute_single(s, 'a') + compute_single(s, 'b') + compute_single(s, 'c') + compute_pairs(s, 'a', 'b') + compute_pairs(s, 'b', 'c') + compute_pairs(s, 'c', 'a') + compute_triples(s); cout << res << "\n"; }
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 | #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; #define SIZE(a) ((int)a.size()) ll compute_single(string &s, char a) { ll res = 0; int len = 0; for(char c : s) { if(c == a) { len++; } else { len=0; } res+=len; } return res; } ll compute_pairs(string &s, char a, char b) { map<int, int> m; m[0] = 0; int diff = 0; ll res = 0; vector<int> dp(SIZE(s)+1); for(int i=0; i < SIZE(s); i++) { char c = s[i]; if(c == a || c == b) { if(c == a) { diff++; } else { diff--; } if(m.count(diff)) { dp[i+1] = dp[m[diff]]+1; } m[diff] = i+1; res+=dp[i+1]; } else { diff = 0; m.clear(); m[0] = 0; } } return res; } ll compute_triples(string &s) { map<pii, int> m; int diff1=0, diff2=0; ll res = 0; vector<int> dp(SIZE(s)+1); m[{0, 0}] = 0; for(int i=0; i < SIZE(s); i++) { char c = s[i]; if(c == 'a') { diff1++; diff2++; } else if(c == 'b') { diff1--; } else { diff2--; } if(m.count({diff1, diff2})) { dp[i+1] = dp[m[{diff1, diff2}]]+1; } m[{diff1, diff2}] = i+1; res+=dp[i+1]; } return res; } int main() { ios_base::sync_with_stdio(0); string s; cin >> s; ll res = compute_single(s, 'a') + compute_single(s, 'b') + compute_single(s, 'c') + compute_pairs(s, 'a', 'b') + compute_pairs(s, 'b', 'c') + compute_pairs(s, 'c', 'a') + compute_triples(s); cout << res << "\n"; } |