Solution
正难则反,用贡献法
不妨考虑每个位置的字母如果能对当前子串做出贡献的话,那么这个子串中就不能再包含与当前位置相同的字母了,从当前字母分别向左和向右找,找到第一个与当前位置相同字母的位置。假设当前位置为$j$
,左边第一个与当前字母相同的位置为$i$,右边第一个与当前字母相同的位置为$k$
,那么在区间$(i+1,k−1)$仅包含位置j的子串的个数即为$(j−i)∗(k−j)$个,而每个子串中位置为$j$
的字母都能贡献1,那么总贡献就是$(j−i)∗(k−j)$。最后只要从头到尾算出每个位置做出的贡献相加即可求出答案。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
typedef long long ll;
char s[N];
int pos[26];
int l[N],r[N]; // l[i]表示第i位的字母向左扫第一次出现的位置,r[i]表示第i位的字母向右扫第一次出现的位置
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> s + 1;
int n = strlen(s + 1);
//求每个字母向左扫第一次出现的位置
for (int i = 1;i <= n;i ++)
{
int x = s[i] - 'a';
l[i] = pos[x];
pos[x] = i;
}
//求每个字母向右扫第一次出现的位置
for (int i = 0;i < 26;i ++) pos[i] = n + 1; //初始化右边界
for (int i = n;i;i --)
{
int x = s[i] - 'a';
r[i] = pos[x];
pos[x] = i;
}
ll ans = 0;
for (int i = 1;i <= n;i ++)
ans += (ll) (i - l[i]) * (ll)(r[i] - i);
cout << ans << "\n";
}