线性动态规划：统计只含单一字符的最长子串

题目描述
给定一个字符串s，统计其中所有只包含单一字符的子串的个数。注意，这里统计的是子串的个数而非最长长度。例如，字符串"aaabb"中，只含单一字符的子串包括："a"出现3次，"aa"出现2次，"aaa"出现1次，"b"出现2次，"bb"出现1次，总共3+2+1+2+1=9个。

解题过程

步骤1：理解问题与观察规律
我们需要统计所有由相同字符组成的连续子串的数量。关键观察是：如果一个字符连续出现n次，那么：

• 长度为1的子串有n个
• 长度为2的子串有n-1个
• 长度为3的子串有n-2个
• ...
• 长度为n的子串有1个

所以，连续出现n次的相同字符，能够贡献的子串总数为：1 + 2 + 3 + ... + n = n(n+1)/2

步骤2：设计动态规划状态
我们可以定义dp[i]表示以第i个字符结尾的、只含单一字符的最长子串的长度。

状态转移方程：

• 如果s[i] == s[i-1]，那么dp[i] = dp[i-1] + 1
• 如果s[i] ≠ s[i-1]，那么dp[i] = 1

步骤3：计算子串总数
对于每个位置i，dp[i]表示以i结尾的、只含单一字符的最长子串长度。那么以i结尾的、只含单一字符的子串个数正好等于dp[i]。

因此，总子串数 = Σdp[i] (i从0到n-1)

步骤4：详细示例分析
以"aaabb"为例：

• 索引0: 'a', dp[0] = 1，子串："a"
• 索引1: 'a', dp[1] = dp[0] + 1 = 2，子串："a"(新), "aa"
• 索引2: 'a', dp[2] = dp[1] + 1 = 3，子串："a"(新), "aa", "aaa"
• 索引3: 'b', dp[3] = 1，子串："b"
• 索引4: 'b', dp[4] = dp[3] + 1 = 2，子串："b"(新), "bb"

总子串数 = 1 + 2 + 3 + 1 + 2 = 9

步骤5：算法实现

def countHomogenousSubstrings(s):
    n = len(s)
    if n == 0:
        return 0
    
    dp = [0] * n
    dp[0] = 1
    total = 1
    
    for i in range(1, n):
        if s[i] == s[i-1]:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = 1
        total += dp[i]
    
    return total

步骤6：空间优化
由于dp[i]只依赖于dp[i-1]，我们可以用单个变量代替dp数组：

def countHomogenousSubstrings(s):
    n = len(s)
    if n == 0:
        return 0
    
    total = 1
    current_len = 1
    
    for i in range(1, n):
        if s[i] == s[i-1]:
            current_len += 1
        else:
            current_len = 1
        total += current_len
    
    return total

步骤7：复杂度分析

• 时间复杂度：O(n)，只需遍历字符串一次
• 空间复杂度：O(1)，只使用了常数个额外变量

步骤8：验证与测试
测试用例：

• "aaabb" → 9
• "abbcccaa" → 13
• "xyz" → 3
• "a" → 1
• "" → 0

这个算法高效地统计了所有只含单一字符的子串个数，利用了连续相同字符段会产生等差数列求和数量的子串这一关键规律。