一、題目

對(duì)于一個(gè)字符串S，我們定義S的分值f(S)為S中出現(xiàn)的不同的字符個(gè)數(shù)。
例如f (“aba”) = 2，f (“abc')=3, f("aaa”) = 1。
現(xiàn)在給定一個(gè)字符串S[0...n一1](長(zhǎng)度為n)，請(qǐng)你計(jì)算對(duì)于所有S的非空子串S[i...j](0<i≤j <n)，
f(S[i..j])的和是多少。
輸入一行包含一個(gè)由小寫(xiě)字母組成的字符串 S。
其中，1≤n≤10^5。

二、解題思路

開(kāi)始很容易想到對(duì)每個(gè)位置從開(kāi)頭到結(jié)尾進(jìn)行循環(huán)，但是這樣肯定超時(shí)，所以后來(lái)我又想到用遞歸試試，但是還是超時(shí)了（不過(guò)寫(xiě)出來(lái)挺有成就感，所以最后我再貼出來(lái)紀(jì)念一下）?？戳斯俜浇o出的解析，他給出來(lái)的解法挺妙的。是通過(guò)計(jì)算每個(gè)字母對(duì)這段字符串是否有貢獻(xiàn)算出來(lái)的。注意字符串?dāng)?shù)組從一開(kāi)始記錄

因?yàn)樵谝粋€(gè)字符串中只有一個(gè)字母會(huì)對(duì)字符串做出貢獻(xiàn)，所以我們定義只有最右邊的字母會(huì)對(duì)字符串做出貢獻(xiàn)，我們看第i個(gè)字母，這樣這個(gè)字母對(duì)整個(gè)結(jié)果所做出的貢獻(xiàn)就是從開(kāi)頭到這個(gè)字母右邊第一次出現(xiàn)與之相同的字母之前且包含這個(gè)位置的所有組合的數(shù)量。具體就是開(kāi)頭開(kāi)始，與該字母右邊到第一次出現(xiàn)與第i個(gè)字母相同的位置這段中所有的長(zhǎng)度的組合。說(shuō)的很繞，我也快繞進(jìn)去了，舉個(gè)例子，如對(duì)于字符串‘a(chǎn)babc’，我們來(lái)看位置2的‘b’，他所能做出貢獻(xiàn)的字符串長(zhǎng)度一直到，位置4的‘b’出現(xiàn)，即最長(zhǎng)的‘a(chǎn)ba’中位置2的b可以做出貢獻(xiàn)，再長(zhǎng)就不行了，那么他能做出貢獻(xiàn)的所有字符串是那些呢？我們可以分組一下，在‘b’左邊一組（包括‘b’），在’b‘右邊一組（也包括’b‘），這樣兩組長(zhǎng)度乘起來(lái)，就是所有組合的數(shù)量（可以這樣來(lái)理解，從左邊第i個(gè)開(kāi)始，到右邊第j個(gè)結(jié)束），即’ab‘，’b‘，’aba‘，’ba‘

所以我們定義一個(gè)suf[N]數(shù)組，代表第i個(gè)位置的字母右邊第一次出現(xiàn)的位置，第i位置的字母對(duì)答案做出的貢獻(xiàn)就是i*（suf[i]-i)。最終答案就是把每個(gè)位置的貢獻(xiàn)加起來(lái)。

因?yàn)榍笊弦淮纬霈F(xiàn)的位置，所以要把這個(gè)字母上一次出現(xiàn)的位置記錄下來(lái)。設(shè)標(biāo)志數(shù)組last[26],代表字母從右邊開(kāi)始上一次出現(xiàn)的位置

求suf的代碼如下

三、完整代碼

四、遞歸代碼（會(huì)超時(shí)）