题目描述

c++版

算法1

时间复杂度$O(n)$

参考文献

https://www.acwing.com/file_system/file/content/whole/index/content/1435008/

易错点:之所以字符从1开始是因为0*任何数都为0,计算不了首字母的贡献度。

C++ 代码

#include<bits/stdc++.h>
using namespace std;

unordered_map<char,int> last;
int main(){
    string s;
    long long ans = 0;
    cin>>s;
    int len = s.size();
    s = ' '+s;
    for(int i=1;i<=len;i++){
       ans += 1ll * (i-(last[s[i]]+1)+1)* (len-i+1);
       last[s[i]] = i; 
    }
    cout<<ans;

    return 0;
}