<> Substring score

Title Description
For a string SS, We define SS Score of f(S)f(S) by SS The number of characters that appear exactly once in the . for example f(“aba”) = 1,f(“abc”) =
3, f(“aaa”) = 0f(“aba”)=1,f(“abc”)=3,f(“aaa”)=0.

Now give a string S0⋯n−1,（ Count Reg n,1≤n≤10^5
）, Please calculate for all SS Non empty substring of Si…j(0 ≤ i ≤ j < n)(0≤i≤j<n),f(S i⋯j) What is the sum of .

Enter description
The input line contains a string of lowercase letters SS.

Output description
Output an integer to represent the answer .

input
ababc
output
21
Operational limits
Maximum running time ：1s
Maximum running memory : 256M
thinking 1：

So the outer cycle i Is the starting position control ;
Inner layer j from i reach n, And there is no repetition score++, And ans+=score;
There is a duplicate （ Namely vis[j]==1 Time ）score–, And ans+=score;
code:（60%）
#include<stdio.h> #include<iostream> #include<cstring> using namespace std;
char s[100003]; int vis[27]; int main() { scanf("%s",s); int len=strlen(s); int
sum=0; for(int i=0;i<len;i++){ memset(vis,0,sizeof vis); int score=0; for(int j=
i;j<len;j++){ if(vis[s[j]-'a']==0){ score++; sum+=score; vis[s[j]-'a']++; }else{
if(score>=1&&vis[s[j]-'a']==1){ vis[s[j]-'a']++; score--; } sum+=score; } } }
printf("%d",sum); return 0; }
thinking 2：
For each character, find its pair sum Contribution value of ;
Careful observation will find ： Contribution value of each character =（ Current bottom index- Previous same character subscript ）*（ Next same character subscript - Current subscript index）
If there is no same character before , By default, the subscript of the previous same character is 0;
If the same character is not followed , By default, the subscript of the last same character is s_length;

Add up all the character contribution values together !
accept code：
#include<iostream> #include<string.h> #include<string> using namespace std; #
define MAX 100003 int main() { string s; int pre[MAX],next[MAX],a[27]; cin>>s; s
="0"+s; int len=s.length(); for(int i=0;i<27;i++){ a[i]=0; } for(int i=1;i<len;i
++){ int index=s[i]-'a'; pre[i]=a[index]; a[index]=i; } for(int i=0;i<27;i++){ a
[i]=len; } for(int i=len-1;i>=1;i--){ int index=s[i]-'a'; next[i]=a[index]; a[
index]=i; } long long int ans=0; for(int i=1;i<len;i++){ ans+=(long long)((i-pre
[i])*(next[i]-i)); } printf("%lld",ans); return 0; }

Technology
Daily Recommendation
views 1