算法

(贡献法) $O(n)$

用vector数组把所有字符的位置记录下来, 出现过的字符要在头加入-1, 尾加入长度n(防越界).
处理完后循环遍历每个字母, 如果该字母数组不空, 则遍历该字母的所有出现下标, 用v表示这个字母当前的下标, u表示上一次出现这个字母的下标, k表示下一次出现这个位置的下标.
因此这个字母对答案的贡献就是ans += (v - u) * (k - v)

C++ 代码

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

vector<int> pos[26];
string s;
ll ans;

int main()
{
    cin >> s;
    int n = s.size();
    for (int i = 0; i < n; i ++) {
        int t = s[i] - 'a';
        if (pos[t].size() == 0) {
            pos[t].push_back(-1);
            pos[t].push_back(i);
        } else {
            pos[t].push_back(i);
        }
    }
    for (int i = 0; i < 26; i ++) {
        if (pos[i].size()) pos[i].push_back(n);
    }
    for (int i = 0; i < 26; i ++) {
        if (!pos[i].size()) continue;
        for (int j = 1; j < pos[i].size() - 1; j ++) {
            int u = pos[i][j - 1], v = pos[i][j], k = pos[i][j + 1];
            ans += (ll)(v - u) * (k - v);
        }
    }
    cout << ans;
    return 0;
}