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

题目描述：
给定一个字符串s，统计其中同构子字符串的数目。同构子字符串定义为：该子字符串中所有字符都相同。例如，字符串"abbccca"中，同构子字符串包括"a"、"b"、"b"、"c"、"c"、"c"、"a"、"bb"、"ccc"等。

解题过程：

1. 问题分析：

• 我们需要统计所有可能的同构子字符串
• 同构子字符串要求所有字符完全相同
• 一个长度为k的连续相同字符段，可以形成k*(k+1)/2个同构子字符串
• 但直接相加会重复计算，我们需要更系统的方法

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

3. 状态转移方程：

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

4. 统计结果：

• 对于每个位置i，以i结尾的同构子字符串数量正好等于dp[i]
• 因为长度为k的相同字符段，可以形成k个以当前字符结尾的同构子字符串

5. 算法步骤：

初始化：
  dp[0] = 1
  total = dp[0]  // 总同构子字符串数

循环i从1到n-1：
  如果s[i] == s[i-1]:
      dp[i] = dp[i-1] + 1
  否则:
      dp[i] = 1
  total += dp[i]

6. 示例分析：
   字符串"abbccca"：

• i=0: 'a', dp[0]=1, total=1
• i=1: 'b'≠'a', dp[1]=1, total=2
• i=2: 'b'='b', dp[2]=2, total=4
• i=3: 'c'≠'b', dp[3]=1, total=5
• i=4: 'c'='c', dp[4]=2, total=7
• i=5: 'c'='c', dp[5]=3, total=10
• i=6: 'a'≠'c', dp[6]=1, total=11

验证：确实有11个同构子字符串

7. 复杂度分析：

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

这种方法通过动态规划巧妙地避免了重复计算，准确统计了所有同构子字符串的数量。