思路

显然无法统计每一个子串的 $f$ 值。不妨统计每个位置字母的贡献。

就如样例 $S=“ababc”$，第二个 $a$ 会在 $S[2\cdots 5]$ 的范围内产生贡献，这个范围内的子串有 $(3-2+1)\times(5-3+1)=6$ 个，因此产生的贡献是 $6$。

不妨记录下每个字母在字符串中的位置 $pos(i,j)$，表示字母 $i$ 在字符串中第 $j$ 次出现的位置，那么 $S[pos(i,j)]$ 产生的贡献就是 $[pos(i,j)-pos(i,j-1)]\times[pos(i,j+1)-pos(i,j)]$；值得注意的是，端点位置需要特判。将每个位置的贡献累加就是答案。

代码

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: AcWing 2868
Date: 2021 Apr. 4th
Description: Count
*******************************************************************/
#include<cstring>
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
int n;
char s[100003];
vector<ll>pos[26];
int main() {
    cin >> (s + 1);
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        pos[s[i] - 'a'].emplace_back(i);
    }
    ll ans = 0;
    for (int i = 0; i < 26; i++) {
        if (pos[i].size() == 0) {
            continue;
        } else if (pos[i].size() == 1) {
            ans += pos[i].front() * (n - pos[i].front() + 1);
            continue;
        }
        ll l, r;
        l = pos[i].front() - 1;
        r = pos[i][1] - pos[i].front() - 1;
        ans += (l + 1) * (r + 1);
        l = pos[i].back() - *prev(pos[i].end(), 2) - 1;
        r = n - pos[i].back();
        ans += (l + 1) * (r + 1);
        for (int j = 1; j < pos[i].size() - 1; j++) {
            l = pos[i][j] - pos[i][j - 1] - 1;
            r = pos[i][j + 1] - pos[i][j] - 1;
            ans += (l + 1) * (r + 1);
        }
    }
    cout << ans << endl;
    return 0;
}