有幾個同質子字串? Count Num of Homogenous Substrings Leetcode #1759

這題的題目在這裡:Count Number of Homogenous Substrings

題目敘述

題目會給定我們一個字串s，要求我們計算出同質子字串有幾個?

最後，題目要求回傳答案前，必須對10^9+7做除法，取餘數當作最終答案。

測試範例

Example 1:

Input: s = "abbcccaa"
Output: 13
Explanation: The homogenous substrings are listed as below:
"a"   appears 3 times.
"aa"  appears 1 time.
"b"   appears 2 times.
"bb"  appears 1 time.
"c"   appears 3 times.
"cc"  appears 2 times.
"ccc" appears 1 time.
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13.

Example 2:

Input: s = "xy"
Output: 2
Explanation: The homogenous substrings are "x" and "y".

Example 3:

Input: s = "zzzzz"
Output: 15

約束條件

Constraints:

• 1 <= s.length <= 10^5
• s consists of lowercase letters.

演算法

其實由左到右的線性掃描就可以滿足需求

每次迭代，觀察以s[i]為結尾的同質子字串有幾個。

以範例"abbcccaa"為例子

a 貢獻一組a

b 貢獻一組b

下一個 b 貢獻兩組b, bb

c 貢獻一組c

下一個 c 貢獻兩組c, cc

再下一個c 貢獻三組c, cc, ccc

a 貢獻一組a

下一個 a 貢獻兩組a, aa

總共有 1 + 1 + 2 + 1 + 2 + 3 + 1 + 2 = 13 組同質子字串。

每次迭代檢查當下這個字元有沒有和前一個字元重複。

如果有重複，把重複長度+1。

如果沒有重複，把重複長度reset 成1，代表這回合遇到的是新的字元。

每次迭代，把當前貢獻的同質子字串數目累加到result。

最後，result 對 10^9 + 7 做除法 取餘數，回傳最終答案即可。

程式碼

class Solution:
　def countHomogenous(self, s: str) -> int:

　　result, count = 0, 0

　　for i, char in enumerate(s):
　　　if i == 0 or s[i-1] == char:
　　　　# update homogenous substring count, ending at s[i]
　　　　count += 1
　　　else:
　　　　# we meet a new character, different to previous one
　　　　count = 1
　　　
　　　# accumulate total count of homogenous substring
　　　result += count

　　return result % (10**9 + 7)

複雜度分析

時間複雜度:

O(n) 使用一次線性掃描，長度和原本的輸入字串一樣長O(n)。

空間複雜度:

O(1) 使用到的都是固定尺寸的臨時變數，為常數級別。

關鍵知識點

每次迭代，觀察以s[i]為結尾的同質子字串有幾個。

Reference:

[1] Count Number of Homogenous Substrings - LeetCode