主題
題目連結(jié)：
題目意譯：
一個字串的「魅力值」為該字串中的字元種類數(shù)。
例如說，"abbca" 的魅力值為 3，因為它有 3 種字元：'a' 、 'b' 和 'c'。
給定一字串 s，回傳它所有子字串的魅力值之總和。
一個子字串為一字串中的連續(xù)字元序列。
限制：
1 ≦ s.length ≦ 10 ^ 5
s 由小寫英文母組成。
範(fàn)例測資：
範(fàn)例 1：
輸入： s = "abbca"
輸出： 28
解釋： 以下為 "abbca" 的子字串：
- 長度 1 的子字串："a" 、 "b" 、 "b" 、 "c" 、 "a" 依序有著魅力值 1 、 1 、 1 、 1 和 1?？偤蜑?5。
- 長度 2 的子字串："ab" 、 "bb" 、 "bc" 、 "ca" 依序有著魅力值 2 、 1 、 2 和 2?？偤蜑?7。
- 長度 3 的子字串："abb" 、 "bbc" 、 "bca" 依序有著魅力值 2 、 2 和 3。總和為 7。
- 長度 4 的子字串："abbc" 、 "bbca" 依序有著魅力值 3 和 3?？偤蜑?6。
- 長度 5 的子字串："abbca" 有著魅力值 3?？偤蜑?3。
總和 5 + 7 + 7 + 6 + 3 = 28。
範(fàn)例 2：
輸入： s = "code"
輸出： 20
解釋： 以下為 "code" 的子字串：
- 長度 1 的子字串："c" 、 "o" 、 "d" 、 "e" 依序有著魅力值 1 、 1 、 1 和 1。總和為 4。
- 長度 2 的子字串："co" 、 "od" 、 "de" 依序有著魅力值 2 、 2 和 2。總和為 6。
- 長度 3 的子字串："cod" 、 "ode" 依序有著魅力值 3 和 3?？偤蜑?6。
- 長度 4 的子字串："code" 有著魅力值 4?？偤蜑?4。
總和 4 + 6 + 6 + 4 = 20。
解題思維：
考慮字串 s = "abbbaabb" 的最後一個字母，有多少子字串以最後一個字母作為結(jié)尾？答案是：
b
bb
abb
aabb
baabb
bbaabb
bbbaabb
abbbaabb
以上八個子字串，也就是從最後一個字母往左一直延伸。而魅力值分別為：
1
1
2
2
2
2
2
2
魅力值從 1 → 2 的變化發(fā)生於往左延伸碰到第一個 a 的時候，該位置索引值 5，因此接下來延伸到開頭為止都會有 a 存在於子字串中?？傆嫊?5 + 1 個子字串（如上所示）。
而實際上第一個子字串 "b" 可以視為從這個位置開始有了 b 存在（索引值 7），因此接下來 7 + 1 個子字串都會有著 b 存在。
因此以最後一個字母作為結(jié)尾的子字串們，其總魅力值為字元 a 貢獻(xiàn)的 6 以及 b 貢獻(xiàn)的 8，總計 14。
不過以上結(jié)論並非只適用於最後一個字母，也不只適用於兩種字母的情況。實際上替換成任何字母 s[i] 都是可行的，而且有任意種類的字母存在也行（哪怕只有一種字母也是）。
而且因為我們討論的是以 s[i] 作為結(jié)尾的子字串，因此 s[0] 、 s[1] 、…… 之間討論到的子字串不會重複。
並且可以看到討論中我們需要每一種字母「最後」出現(xiàn)在哪裡，也就是說它們在 s[0] ～ s[i] 中位置索引值最大者。
因此我們可以從 s[0] 開始，一路掃到結(jié)尾。期間可以用一個陣列來記錄每一種字母最後出現(xiàn)的位置，當(dāng)遇到 s[i] 就把對應(yīng)的字元的「最後出現(xiàn)」更新成 i。之後就可以按著上面的討論算出 s[i] 負(fù)責(zé)的子字串之總魅力值。
最後把所有 s[i] 的總魅力值加總即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
