算法1
(暴力枚举) $O(n^2)$
先统计出每一个小写字符出现的下标;
存入a中,a[i]存放的是字符i+’a’在s中出现的所有下标;
对于每个下标,算其对答案的贡献 :
设x是该字符与上一个相同字符中间相隔的字符数量;
设y是该字符与上一个相同字符中间相隔的字符数量;
那么贡献就是 (x+1)*(y+1) ;
因为对于该字符,左边选取相邻串的长度可能有(0,1,2,3…x)共x+1中,右边同理;
所以两者相乘即是对答案的贡献 ;
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
vector<int> a[26] ;
LL get(int x , int y){
return 1LL * (x+1) * (y+1) ;
}
int main(){
string s ; cin >> s ;
int n = s.size() ;
LL ans = 0 ;
for(int i=0;i<n;i++){
a[(int)(s[i]-'a')].push_back(i) ;
}
for(int i=0;i<26;i++){
auto vec = a[i] ;
int m = vec.size() ;
if(m==0) continue ;
if(m==1){
ans += get(vec[0] , n-vec[0]-1) ;
continue ;
}
for(int j=0;j<m;j++){
int xx, yy ;
if(j==0) xx = vec[0] ,yy = vec[1] - vec[0] - 1;
else if(j==m-1) xx = vec[j] - vec[j-1] - 1, yy = n - vec[j] - 1 ;
else xx = vec[j] - vec[j-1] - 1 , yy = vec[j+1] - vec[j] - 1 ;
ans += get(xx , yy) ;
}
}
cout << ans << endl ;
}