LeetCode 题解工作台
统计同质子字符串的数目
给你一个字符串 s ，返回 s 中 同质子字符串 的数目。由于答案可能很大，只需返回对 10 9 + 7 取余 后的结果。 同质字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同质字符串。 子字符串 是字符串中的一个连续字符序列。 示例 1： 输入： s = "abbcccaa"…
2
题型
8
代码语言
3
相关题
当前训练重点
中等 · 数学·string
答案摘要
遍历字符串 ，用指针 指向当前字符，指针 指向下一个不同的字符，那么 区间内的字符都是相同的，假设 ，那么该区间内的同构子字符串个数为 $\frac{(1 + cnt) \times cnt}{2}$，将其累加到答案中即可。继续遍历，直到指针 到达字符串末尾。 遍历完字符串 后，返回答案即可。注意答案的取模操作。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数学·string 题型思路
题目描述
给你一个字符串 s ，返回 s 中 同质子字符串 的数目。由于答案可能很大，只需返回对 109 + 7 取余 后的结果。
同质字符串 的定义为：如果一个字符串中的所有字符都相同，那么该字符串就是同质字符串。
子字符串 是字符串中的一个连续字符序列。
示例 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
提示：
1 <= s.length <= 105s由小写字符串组成。
解题思路
方法一：双指针
遍历字符串 ，用指针 指向当前字符，指针 指向下一个不同的字符，那么 区间内的字符都是相同的，假设 ，那么该区间内的同构子字符串个数为 ，将其累加到答案中即可。继续遍历，直到指针 到达字符串末尾。
遍历完字符串 后，返回答案即可。注意答案的取模操作。
时间复杂度 ，空间复杂度 。其中 为字符串 的长度。
class Solution:
def countHomogenous(self, s: str) -> int:
mod = 10**9 + 7
i, n = 0, len(s)
ans = 0
while i < n:
j = i
while j < n and s[j] == s[i]:
j += 1
cnt = j - i
ans += (1 + cnt) * cnt // 2
ans %= mod
i = j
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for knowledge of string manipulation and efficient counting.
- question_mark
Evaluate the candidate's understanding of mathematical patterns and their application to this problem.
- question_mark
Check if the candidate can handle large inputs by optimizing the solution to O(n) time complexity.
常见陷阱
外企场景- error
Forgetting to take the sum modulo 10^9 + 7 at each step can result in overflow errors.
- error
Confusing the formula for the number of substrings, especially with blocks of length 1.
- error
Not considering edge cases like strings with only one character or strings with all distinct characters.
进阶变体
外企场景- arrow_right_alt
Change the problem to return the total number of homogenous substrings of length greater than 1.
- arrow_right_alt
Modify the problem to work with strings containing uppercase letters.
- arrow_right_alt
Ask the candidate to solve the problem using a sliding window approach.