long substrCount(int n, const string& s) {
    long total = 0;
    vector<vector<int>> con1(n + 1, vector<int>(26));
    vector<int> con2(n + 1, -1);
    for (int i = 1; i <= n; ++i) {
        con1[i][s[i-1] - 'a'] = con1[i-1][s[i-1]-'a'] + 1;
        total = total + con1[i][s[i-1]-'a'];
    }
    for (int i = 3; i <= n; ++i) {
        if (s[i-1] != s[i-2] and s[i-1] == s[i-3]) con2[i] = 3;
        else if (s[i-1] == s[i-2] and con2[i-1] != -1 and i-con2[i-1]-1 > 0 and s[i-con2[i-1]-2] == s[i-1]) {
            con2[i] = con2[i-1] + 2;
        }
        if (con2[i] != -1) ++total;
    }
    return total;
}