1759. 统计同质子字符串的数目#

题目描述#

给你一个字符串 s，返回同质子字符串的数目。

由于答案可能很大，返回答案需要对 10^9 + 7 取模。

同质字符串的定义是：若一个字符串中所有字符都相同，则称它是同质字符串。

同质子字符串的定义是：如果一个子字符串是同质字符串，则称它是同质子字符串。

示例 1：

1
输入：s = "abbcccaa"
2
输出：13
3
解释：同质子字符串如下所列：
4
"a"   出现 3 次。
5
"aa"  出现 1 次。
6
"b"   出现 2 次。
7
"bb"  出现 1 次。
8
"c"   出现 3 次。
9
"cc"  出现 2 次。
10
"ccc" 出现 1 次。
11
3 + 1 + 2 + 1 + 3 + 2 + 1 = 13

示例 2：

1
输入：s = "xy"
2
输出：2

提示：

1 <= s.length <= 10^5

解题思路#

核心思想#

与 1513 题完全同构。把字符串按连续相同字符分成段，对每段长度 k，其内部可形成的同质子串数量为 k*(k+1)/2，全部相加并对 10^9+7 取模。

段贡献示意（s = “abbcccaa”）：

1
a | bb | ccc | aa
2
1    3     6    3   → 总计 13

算法步骤#

初始化 ans = 0，i = 0。
当 i < n 时：
- j = i，扩展 while j+1 < n and s[j+1] == s[i]；
- 段长 k = j - i + 1，ans += k*(k+1)//2，i = j + 1。
返回 ans % (10^9+7)。

逐步举例#

以 s = "abbcccaa" 为例：

段	区间	长度 k	贡献 k(k+1)/2
a	[0,0]	1	1
bb	[1,2]	2	3
ccc	[3,5]	3	6
aa	[6,7]	2	3

合计 1 + 3 + 6 + 3 = 13。

复杂度分析#

时间复杂度：O(N)，单次线性扫描。
空间复杂度：O(1)。

代码实现#

1
class Solution:
2
    def countHomogenous(self, s: str) -> int:
3
        MOD = 10 ** 9 + 7
4
        ans = 0
5
        n = len(s)
6
        i = 0
7
        while i < n:
8
            j = i
9
            while j + 1 < n and s[j + 1] == s[i]:
10
                j += 1
11
            k = j - i + 1
12
            ans = (ans + k * (k + 1) // 2) % MOD
13
            i = j + 1
14
        return ans

1
import sys
2
from pathlib import Path
3

4
sys.path.insert(0, str(Path(__file__).parent))
5
import unittest
6

7
from solution import Solution
8

9

10
class TestSolution(unittest.TestCase):
11
    def test_example1(self):
12
        self.assertEqual(Solution().countHomogenous("abbcccaa"), 13)
13

14
    def test_example2(self):
15
        self.assertEqual(Solution().countHomogenous("xy"), 2)
16

17

18
if __name__ == '__main__':
19
    unittest.main()