一、题目

对于一个字符串S，我们定义S的分值f(S)为S中出现的不同的字符个数。
例如f (“aba”) = 2，f (“abc')=3, f("aaa”) = 1。
现在给定一个字符串S[0...n一1](长度为n)，请你计算对于所有S的非空子串S[i...j](0<i≤j <n)，
f(S[i..j])的和是多少。
输入一行包含一个由小写字母组成的字符串 S。
其中，1≤n≤10^5。

二、解题思路

开始很容易想到对每个位置从开头到结尾进行循环，但是这样肯定超时，所以后来我又想到用递归试试，但是还是超时了（不过写出来挺有成就感，所以最后我再贴出来纪念一下）。看了官方给出的解析，他给出来的解法挺妙的。是通过计算每个字母对这段字符串是否有贡献算出来的。注意字符串数组从一开始记录

因为在一个字符串中只有一个字母会对字符串做出贡献，所以我们定义只有最右边的字母会对字符串做出贡献，我们看第i个字母，这样这个字母对整个结果所做出的贡献就是从开头到这个字母右边第一次出现与之相同的字母之前且包含这个位置的所有组合的数量。具体就是开头开始，与该字母右边到第一次出现与第i个字母相同的位置这段中所有的长度的组合。说的很绕，我也快绕进去了，举个例子，如对于字符串‘ababc’，我们来看位置2的‘b’，他所能做出贡献的字符串长度一直到，位置4的‘b’出现，即最长的‘aba’中位置2的b可以做出贡献，再长就不行了，那么他能做出贡献的所有字符串是那些呢？我们可以分组一下，在‘b’左边一组（包括‘b’），在’b‘右边一组（也包括’b‘），这样两组长度乘起来，就是所有组合的数量（可以这样来理解，从左边第i个开始，到右边第j个结束），即’ab‘，’b‘，’aba‘，’ba‘

所以我们定义一个suf[N]数组，代表第i个位置的字母右边第一次出现的位置，第i位置的字母对答案做出的贡献就是i*（suf[i]-i)。最终答案就是把每个位置的贡献加起来。

因为求上一次出现的位置，所以要把这个字母上一次出现的位置记录下来。设标志数组last[26],代表字母从右边开始上一次出现的位置

求suf的代码如下

三、完整代码

四、递归代码（会超时）