线性动态规划：统计同构子字符串的个数

题目描述
给定一个字符串 s，定义同构子字符串为满足以下条件的子串：

• 子串中的所有字符都相同。

要求统计 `s`` 中所有同构子字符串的个数，不同起始和结束位置视为不同的子串。

示例
输入："abbcccba"
输出：20
解释：

• 长度为1的同构子串有8个（每个字符单独为一个子串）。
• 长度为2的同构子串有4个（"bb"、两个"cc"、注意"cc"出现了两次，分别在位置(3,4)和(4,5)）。实际上，"bb"是1个（位置2~3），"cc"是2个（位置4~5和5~6，但这两个"cc"是重叠的，都统计）。我们稍后会详细分析。
• 长度为3的同构子串有2个（"ccc"出现了两次，位置(4,6)和(5,7)？注意"ccc"长度为3，在"ccc"中，可以取起始索引4、长度3，以及起始索引5、长度3，但这样会包含字符'b'？不对，我们仔细列出所有同构子串）。

为了避免混淆，我们先明确统计规则：
同构子串：子串中所有字符相同。例如"a"、"bb"、"ccc"都是。
统计时，只要起始和结束位置不同，就算不同的子串。
例如"aaa"中：

• 长度为1的："a"（索引0）、"a"（索引1）、"a"（索引2）→ 3个。
• 长度为2的："aa"（索引0~1）、"aa"（索引1~2）→ 2个。
• 长度为3的："aaa"（索引0~2）→ 1个。
  总共6个。

对于"abbcccba"，我们后面用动态规划方法来计算，验证答案是20。

解题思路
我们可以用线性动态规划解决。
定义 dp[i] 表示以字符 s[i] 结尾的同构子串的个数。
注意：以 s[i] 结尾的同构子串，必须所有字符相同，且连续。
转移方程：

• 如果 s[i] == s[i-1]，那么以 s[i] 结尾的同构子串可以在以 s[i-1] 结尾的同构子串的基础上，末尾再添加 s[i] 得到，另外还包含一个单独的字符 s[i] 本身。实际上，数量是 dp[i-1] + 1。
• 如果 s[i] != s[i-1]，那么以 s[i] 结尾的同构子串只有它自己（长度为1），即 dp[i] = 1。

状态转移方程：

dp[i] = dp[i-1] + 1,  if s[i] == s[i-1]
        1,            if s[i] != s[i-1]

初始条件：dp[0] = 1（第一个字符自身构成一个同构子串）。

最终答案：sum(dp[0..n-1])，因为每个 dp[i] 统计了以 i 结尾的所有同构子串，所有结尾位置的不同子串总和就是总个数。

逐步计算示例
s = "abbcccba"，n=8。

• i=0: dp[0] = 1（子串"a"）
• i=1: s[1]='b' ≠ s[0]='a' → dp[1]=1（子串"b"）
• i=2: s[2]='b' == s[1]='b' → dp[2]=dp[1]+1=2（子串"b"（索引2单独）、"bb"（索引1~2））
• i=3: s[3]='c' ≠ s[2]='b' → dp[3]=1（子串"c"）
• i=4: s[4]='c' == s[3]='c' → dp[4]=dp[3]+1=2（子串"c"（索引4单独）、"cc"（索引3~4））
• i=5: s[5]='c' == s[4]='c' → dp[5]=dp[4]+1=3（子串"c"（索引5单独）、"cc"（索引4~5）、"ccc"（索引3~5））
• i=6: s[6]='b' ≠ s[5]='c' → dp[6]=1（子串"b"）
• i=7: s[7]='a' ≠ s[6]='b' → dp[7]=1（子串"a"）

dp数组：[1,1,2,1,2,3,1,1]
总和 = 1+1+2+1+2+3+1+1 = 12？但示例说答案是20，哪里出了问题？

我们仔细检查：示例中给出的输出是20，但按照上述dp求和是12，显然不对。
原因：题目要求统计所有同构子字符串的个数，包括不以 i 结尾的子串。我们的dp只统计了以 i 结尾的子串，但这样确实覆盖了所有同构子串吗？
是的，因为任何同构子串都有唯一的结尾位置，所以每个同构子串恰好被统计一次（在其结尾位置）。所以总和应该是所有同构子串的数量。
那我们计算12，但示例说20，说明示例的20可能是错的，或者我理解有误。

让我们直接列出s="abbcccba"的所有同构子串：
索引0: 'a' → 1个（"a"）
索引1: 'b' → 1个（"b"）
索引2: 'b' → 但以索引2结尾的同构子串有："b"（索引2）、"bb"（索引1~2）→ 2个
索引3: 'c' → 1个（"c"）
索引4: 'c' → 2个（"c"索引4单独、"cc"索引3~4）
索引5: 'c' → 3个（"c"索引5单独、"cc"索引4~5、"ccc"索引3~5）
索引6: 'b' → 1个（"b"）
索引7: 'a' → 1个（"a"）

但注意："cc"还出现在索引3~4，已经统计在i=4的dp[4]中（"cc"索引3~4），i=5的"cc"索引4~5是另一个"cc"。
另外"ccc"索引3~5是以i=5结尾，已经统计。

再检查更长的情况：
实际上，对于连续的相同字符段，长度为L，它包含的同构子串总数为 L*(L+1)/2。
字符串"abbcccba"：

• 段1: "a" L=1 → 1
• 段2: "bb" L=2 → 3
• 段3: "ccc" L=3 → 6
• 段4: "b" L=1 → 1
• 段5: "a" L=1 → 1

总和 = 1+3+6+1+1=12。
所以正确答案应该是12，不是20。

可能原示例的20是笔误，或者是另一个类似题（统计同构子串个数，但定义不同）。

但不管怎样，我们的dp方法正确，并且时间复杂度O(n)，空间复杂度O(1)（可以只保留前一个dp值）。

算法步骤

1. 初始化：prev = 1, total = 1（i=0的情况）。
2. 从 i=1 到 n-1：
   • 如果 s[i] == s[i-1]，则 curr = prev + 1，否则 curr = 1。
   • total += curr。
   • prev = curr。
3. 返回 total。

代码实现（Python）

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

验证
s = "abbcccba" → 计算：
i=1: curr=1, total=2
i=2: curr=2, total=4
i=3: curr=1, total=5
i=4: curr=2, total=7
i=5: curr=3, total=10
i=6: curr=1, total=11
i=7: curr=1, total=12

输出12，正确。

思考扩展
如果题目改为：统计所有长度至少为k的同构子串个数，可以在dp过程中累加长度≥k的贡献。
设当前连续相同字符长度为L，则长度为k, k+1, …, L 的子串个数为 L-k+1（如果L≥k）。
可以在遇到字符变化时，累加 (L-k+1) 到答案（如果L≥k）。

复杂度：O(n) 时间，O(1) 额外空间。