算法1

(找规律) $O(n)$

子串 f值
a     1
ab    2
aba   2
abab  2
ababc 3
 b    1
 ba   2
 bab  2
 babc 3
  a   1
  ab  2
  abc 3
   b  1
   bc 2
    c 1

通过样例的解释以及观察，我们可以发现以第i个字符为起点的字串分值和是以第i-1个字符为起点得字符串的分值和减去第i-1个字符的贡献得来的。
贡献：指字符在以其为起点构成得所有字符串中出现的次数

例如：
 字符串bdc以b为起点构成的字符串
 b
 bd
 bdc
 则b的贡献是3

所以如果不考虑字符间有重复的话，那么以第i个字符为起点的分值和就可以用以第i-1个字符为起点的分值和减去字符串长度与第i-1个字符的坐标差(因为第i-1个字符可以最多可以构成长度为len-(i-1)的字符串,len是字符串总长度,所以其可以组成len-(i-1)个子串)得到。

但是 这个规律只适用于当前字符间无重复,对于有重复的举个例子吧

 例如aba
 a     1
 ab    2
 aba   2
  b    1
  ba   2 
   a   1

在第2个a出现之前以b为起点的分值和相对于以a为起点的分值和减少的量是a的贡献，但是第2个a出现后，第2个a填补了第一个a的贡献值，所以实际减少的值是第2个a出现之前的第一个a的贡献值(即a,ab中a的贡献)。
也即以b为起点的分值和相对以第一个a为起点的分值和减少了(a,ab)中a的贡献，因为ba中第2个a填补了第一个a的贡献所以这个字串中a的贡献并未减少。

所以当有重复的字符时，以第i个字符为起点的分值和是以第i-1个字符为起点的分值和-第i-1个字符在以第i个字符为起点的子串中第一次出现位置的坐标差(这里坐标差意思已经在上述解释过)。

综上
1.对于无重复的字符串，相对于上一个字符的分值和减少删掉以当前字符为起点的字符串长度。
2.对于有重复的字符串，相对于上一个字符的分值和减少两个重复字符之间的距离。

时间复杂度

O(n)

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N=1e5+10;

unordered_map<char,int> st;//记录每个字符出现的次数
vector<char> w;//记录每个字符
vector<int> loc[30];//记录每个字符的位置
char s[N];
ll sum1,pre;
int len;

int main()
{
    cin>>s+1;
    len=strlen(s+1);
    //预处理以第1个字符为起点的分值和
   for(int i=1;i<=len;i++)
   {
   if(!st[s[i]]) sum1+=pre+1,pre+=1,w.push_back(s[i]);
   else sum1+=pre;
   st[s[i]]++;
   loc[s[i]-'a'].push_back(i);//将每个字符映射成数字
   }

   for(int i=0;i<w.size();i++)//逆置每个字符的位置,方便将使用过和当前使用着的字符的位置pop掉则最后一个位置就是字符的重复位置
   reverse(loc[w[i]-'a'].begin(),loc[w[i]-'a'].end());

   pre=sum1;//由于第i-1个字符的分值和需要用到第i次的分值和所以pre记录第i次的分值和
   for(int i=2;i<=len;i++)
   {
       st[s[i-1]]--;
       loc[s[i-1]-'a'].pop_back();
       if(st[s[i-1]]>=1)//如果把第i个字符出现的次数-1后其次数仍然>=1则说明有重复
       {
          int size1=loc[s[i-1]-'a'].size();
           sum1+=pre-(ll)(loc[s[i-1]-'a'][size1-1]-(i-1));
           pre=pre-(ll)(loc[s[i-1]-'a'][size1-1]-(i-1));
       }else if(st[s[i-1]]==0)//无重复
       {
           sum1+=pre-(ll)(len-(i-1)+1);
           pre=pre-(len-(ll)(i-1)+1);
       }
   }

    cout<<sum1;
    return 0;
}