LeetCode 筆記 - 1759. Count Number of Homogenous Substrings

Posted on

題目在此 1759. Count Number of Homogenous Substrings

給定一個字串，請問連續字串中相同字元的子字串有幾個？
因為最後答案可能會很大，所以請回傳答案 mod 10^9 + 7。

解題思維

名詞解說：

  • Depth First Search

同學這題千萬不要用 DFS 下去寫啊！有好好的 O(1) 解法，你用 DFS 就爆炸了。
這題的解法其實很簡單，就是計算每個字元的連續個數，然後加總起來就好了。
那長度為 n 的連續字串有幾個呢？答案是 n * (n + 1) // 2。
最後答案再記得 mod 10^9 + 7 就可以哩！image 106

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def countHomogenous(self, s: str) -> int:

        if (size := len(s)) == 1:
            return 1

        modulo = 10 ** 9 + 7

        result = 0

        prev, count = None, 0
        for c in s:
            if c != prev:
                result += (count + 1) * count // 2
                result %= modulo
                count = 1
                prev = c
            else:
                count += 1

        result += (count + 1) * count // 2
        result %= modulo
            
        return result
image 106

也許你也會想看看