1.统计每个字母出现的位置
2.计算每个位置的贡献

怎么计算贡献？

举个例子：

***a**a***a****

第二个a对答案的贡献就是:

*a
**a     即与前一个a位置差再减一
a*
a**
a***    即与后一个a位置差再减一
*a*
*a**
*a***
**a*
**a**
**a***   即上述两结果的乘积
三部分相加即是每个位置对答案的贡献（别忘了还要加上自身，可以在最后加上长度即可）

优化：
每个位置的贡献只与前后两个位置有关，
可以优化成两个一维的数组，分别记录前后两个位置

AC代码（未优化）

#include <iostream>
#include <vector>
using namespace std;

vector<int> pos[26];    //记录字母出现的位置
int main() {
    string s;
    cin >> s;
    int lgh = s.length();
    //记录每个字母出现的位置 并在最前和最后分别添加-1 和 lgh（方便计算）
    for(int i = 0; i < lgh; i++) {
        int index = s[i] - 'a';
        if(!pos[index].size())  pos[index].push_back(-1);   //在第一位添加-1
        pos[index].push_back(i);
    }
    //在最后添加lgh
    for(int i = 0; i < 26; i++)
        if(pos[i].size())   pos[i].push_back(lgh);
    //计算答案
    long long ans = 0;  //防溢出
    for(int i = 0; i < 26; i++)
        if(pos[i].size())
            for(int j = 1; j < pos[i].size() -1; j++)   //三部分和
                ans += (pos[i][j] - pos[i][j - 1] - 1) + (pos[i][j + 1] - pos[i][j] -1)
                + 1ll * (pos[i][j] - pos[i][j - 1] - 1) * (pos[i][j + 1] - pos[i][j] - 1);
    ans += lgh; //加上每个单独的字母
    cout << ans << endl;
    return 0;
}