统计同构子字符串的数目问题（进阶版）

题目描述：
给定一个字符串s，统计其中同构子字符串的数目。同构子字符串定义为：该子字符串中所有字符都相同。例如，字符串"aaa"包含6个同构子字符串："a"（3个）、"aa"（2个）、"aaa"（1个）。

解题过程：

1. 问题分析
   我们需要统计字符串中所有字符都相同的连续子串的个数。比如：

• "a"：只有1个同构子串"a"
• "aa"：有3个同构子串（"a"、"a"、"aa"）
• "aaa"：有6个同构子串（3个"a"、2个"aa"、1个"aaa"）

2. 基础解法思路
   我们可以遍历字符串，找到所有连续的相同字符段。对于长度为n的连续相同字符段，它包含的同构子串数量为：1 + 2 + 3 + ... + n = n(n+1)/2

3. 动态规划定义
   定义dp[i]表示以第i个字符结尾的最长同构子串长度。

4. 状态转移方程

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

5. 计算总数目
   对于每个位置i，dp[i]表示以i结尾的同构子串个数。总数目就是所有dp[i]的和。

6. 具体步骤示例
   以字符串"aaabb"为例：

• i=0: dp[0] = 1，总数目=1
• i=1: s[1]=='a'==s[0]，dp[1]=dp[0]+1=2，总数目=1+2=3
• i=2: s[2]=='a'==s[1]，dp[2]=dp[1]+1=3，总数目=3+3=6
• i=3: s[3]=='b'≠s[2]，dp[3]=1，总数目=6+1=7
• i=4: s[4]=='b'==s[3]，dp[4]=dp[3]+1=2，总数目=7+2=9

验证：字符串"aaabb"的同构子串确实有9个。

7. 算法实现

def count_homogenous_substrings(s):
    if not s:
        return 0
    
    n = len(s)
    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

8. 复杂度分析

• 时间复杂度：O(n)，只需要遍历一次字符串
• 空间复杂度：O(n)，可以优化到O(1)只使用变量记录前一个状态

这种方法通过动态规划高效地统计了所有同构子字符串的数目。