2024寒假每日一题全部题解传送门>>

不妨考虑每个位置的字母如果能对当前子串做出贡献的话，那么这个子串中就不能再包含与当前位置相同的字母了，从当前字母分别向左和向右找，找到第一个与当前位置相同字母的位置。假设当前位置为$j$，左边第一个与当前字母相同的位置为$i$，右边第一个与当前字母相同的位置为$k$，那么在区间$(i+1,k-1)$仅包含位置$j$的子串的个数即为$(j-i) * (k-j)$个，而每个子串中位置为$j$的字母都能贡献$1$，那么总贡献就是$(j-i)*(k-j)$。最后只要从头到尾算出每个位置做出的贡献相加即可求出答案。

C++代码：

#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
char s[N];
vector<int> pos[27];

int main()
{
    scanf("%s", s + 1);

    int n = strlen(s + 1);
    for(int i = 1; i <= n; i ++)
    {
        int x = s[i] - 'a' + 1;
        if(!pos[x].size()) pos[x].push_back(0); // 往左边加上哨兵
        pos[x].push_back(i);
    }

    for(int i = 1; i <= 26; i ++) // 往右边加上哨兵
        pos[i].push_back(n + 1);

    LL res = 0;
    for(int i = 1; i <= 26; i ++)
        for(int j = 1; j < pos[i].size() - 1; j ++)
        {
            int l = pos[i][j] - pos[i][j - 1], r = pos[i][j + 1] - pos[i][j];
            res += (LL)l * r; // 乘法原理
        }

    printf("%lld", res);
    return 0;
}