題目連結:
題目意譯:
給定一個字串 s,回傳 s 中「同質」(Homogenous)子字串的數量。由於答案可能太大,先將其模 10 ^ 9 + 7 後再回傳。
一個字串如果只由一種字元組成,則其為「同質」。
一個子字串為一字串中的一個連續字元序列。
限制:
1 ≦ s.length ≦ 10 ^ 5
s 由小寫字母組成。
範例測資:
範例 1:
輸入: s = "abbcccaa"
輸出: 13
解釋: 同質子字串為下列:
"a" 出現了 3 次。
"aa" 出現了 1 次。
"b" 出現了 2 次。
"bb" 出現了 1 次。
"c" 出現了 3 次。
"cc" 出現了 2 次。
"ccc" 出現了 1 次。
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13。
範例 2:
輸入: s = "xy"
輸出: 2
解釋: 同質子字串為 "x" 和 "y"。
範例 3:
輸入: s = "zzzzz"
輸出: 15
解題思維:
因為我們只考慮「同質」的子字串,因此我們只須掃過一次 s 並統計每一種連續字元的出現情形。
例如說對於範例 1 中的 s = "abbcccaa",我們可以將其拆解為 "a" + "bb" + "ccc" + "aa"。
假設現在看到的字元連續出現了 C 次(例如上例中的 "ccc",其中 'c' 出現了 3 次),若只考慮這個子字串以及其自身的子字串(即把該子字串拆得更小),則會有
C × (C + 1) ÷ 2
個同質子字串。
而把所有連續字元的子字串按照上面的方式計算各自擁有同質子字串並加總即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。