难度: Medium
给你一个字符串 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 由小写字符串组成。运行时间: 67 ms
内存: 16.3 MB
class Solution:
def countHomogenous(self, s: str) -> int:
c = 0
last = ''
total = 0
for i in s:
if i != last:
total += (c + 1) * c / 2
last = i
c = 1
else:
c += 1
total += (c + 1) * c / 2
return int(total) % (10 ** 9 + 7)
该题解采用了一次遍历的方法来统计同质子字符串的数量。它通过维护一个计数器 c 来记录当前同质子字符串的长度，当遇到与上一个字符不同的字符时，就计算以前一个字符为结尾的所有同质子字符串的数量，并将计数器 c 重置为 1。该方法利用了等差数列求和公式来快速计算同质子字符串的数量。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def countHomogenous(self, s: str) -> int:
c = 0 # 记录当前同质子字符串的长度
last = '' # 记录上一个字符
total = 0 # 记录总的同质子字符串数量
for i in s:
if i != last:
total += (c + 1) * c / 2 # 计算以 last 为结尾的所有同质子字符串的数量
last = i # 更新 last 为当前字符
c = 1 # 重置计数器 c
else:
c += 1 # 增加计数器 c
total += (c + 1) * c / 2 # 计算以最后一个字符为结尾的所有同质子字符串的数量
return int(total) % (10 ** 9 + 7) # 返回结果对 10^9 + 7 取余后的值
在遇到一个新的字符时，首先需要计算以前一个字符为结尾的所有同质子字符串的数量。这是通过使用计数器c，代表最新的字符连续出现的次数，来实现的。计算完成后，计数器c会被重置为1，表示新字符的开始。然后，更新变量last为当前的新字符，以便在后续的遍历中使用。
等差数列求和公式`(c + 1) * c / 2`用于快速计算连续的同质子字符可以形成的不同长度的子串数量。例如，如果一个字符连续出现c次，那么可以形成c个长度为1的子串，c-1个长度为2的子串，直到1个长度为c的子串。这些可以通过求和公式直接算出总和，避免了多次循环计算的需求，提高了算法的效率。
对最终的同质子字符串总数进行取余操作（使用模数`10^9 + 7`），主要是为了防止计算结果过大导致的整数溢出问题，并且满足某些编程竞赛和工业应用中对结果大小的常见限制。`10^9 + 7`是一个大质数，使用这个数作为模数可以保证结果在一个安全的数值范围内，同时也是满足某些算法竞赛的标准模数。
如果输入字符串s为空，那么在题解的代码中，由于字符串遍历开始前没有特定字符，计数器c初始值为0，并且不会进入循环体。因此，最终的总同质子字符串数量total也将为0。这样的处理意味着空输入字符串会直接返回总数为0，有效地处理了这种边界情况。