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

题目描述

给你一个字符串 s，你需要统计 s 中所有同构子字符串的数量。
一个字符串被称为同构字符串，如果它满足：

1. 所有字符都相同（例如 "aaa"、"xx"）。
2. 字符串长度至少为 1。

注意：

• 子字符串是连续的，不同于子序列。
• 结果可能很大，需对 \(10^9 + 7\) 取模。

示例
输入：s = "abbccc"
输出：13
解释：
同构子串包括：

• 长度为 1："a"、"b"、"b"、"c"、"c"、"c" → 6 个
• 长度为 2："bb"、"cc"、"cc" → 3 个
• 长度为 3："ccc" → 1 个
• 其他不符合的如 "ab" 不算
  总数为 \(6 + 3 + 1 + 3 = 13\)？等一下，我们仔细计算：
  实际上长度为 2 的 "cc" 出现了两次（位置 (4,5) 和 (5,6)）？不对，这里要明确按起始位置不同统计子串，所以：
  列出所有同构子串：
  "a" (1), "b" (2,3), "b" (3) 不行（重复计数）？正确计数方式见下文。

解题过程

1. 理解问题与暴力思路

• 同构子串就是连续相同字符构成的片段。
• 对于每个位置，如果当前字符与前一个相同，则它可以与前一个字符一起形成新的同构子串。
• 暴力法：枚举所有子串，检查是否同构，时间复杂度 \(O(n^3)\)，太慢。

2. 关键观察

• 设字符串为 s，长度为 n。
• 考虑一个由相同字符组成的最大连续段，长度为 len。例如 "aaa" 的 len = 3。
• 在这个段内，长度为 1 的同构子串有 len 个，长度为 2 的有 len-1 个，…，长度为 len 的有 1 个。
• 所以该段内同构子串总数为：

\[\text{sum} = len + (len-1) + \dots + 1 = \frac{len \cdot (len+1)}{2} \]

• 因此问题转化为：找出所有极长连续相同字符段，对每段计算 \(\frac{len \cdot (len+1)}{2}\)，求和即可。

3. 举例验证

s = "abbccc"

• 段1："a"，len=1 → 贡献 \(1\)
• 段2："bb"，len=2 → 贡献 \(3\)
• 段3："ccc"，len=3 → 贡献 \(6\)
  总和 = \(1 + 3 + 6 = 10\)。
  等一下，这个结果和前面示例说的 13 不一致。哪里出错了？

4. 重新审题与发现错误

实际上，示例 s = "abbccc" 的正确总数是 13，不是 10。
让我们手动列出所有按起始和结束位置不同的同构子串：

1. 位置 [0,0] "a"
2. [1,1] "b"
3. [1,2] "bb"
4. [2,2] "b"
5. [3,3] "c"
6. [3,4] "cc"
7. [4,4] "c"
8. [4,5] "cc"
9. [5,5] "c"
10. [3,5] "ccc"
    总数为 10？不对，我数出来 10 个，不是 13。
    这说明我的理解有误。查一下常见题：这是 LeetCode 的 "Count Substrings with Only One Distinct Letter"（统计所有字符都相同的子串数量）。
    实际公式是：每段长度为 len 的贡献确实是 \(\frac{len \cdot (len+1)}{2}\)。
    对于 "abbccc"：
    段 "a"：1
    段 "bb"：2+1=3
    段 "ccc"：3+2+1=6
    总 10。
    所以示例的 13 可能是错误的，或者是另一道题？
    我确认：LeetCode 类似题答案为 10。这里我们按正确逻辑讲解。

5. 动态规划思路

我们可以用 DP 记录以当前位置结尾的同构子串长度，然后累加。

定义：

\[dp[i] = \text{以 s[i] 结尾的连续相同字符的长度} \]

转移：

\[\text{如果 } s[i] == s[i-1]，则 dp[i] = dp[i-1] + 1 \]

\[ \text{否则 } dp[i] = 1 \]

那么以 s[i] 结尾的同构子串数量正好是 dp[i]（因为它可以构成长度为 1..dp[i] 的子串，每个都以 i 结尾）。

最终答案：

\[\text{ans} = \sum_{i=0}^{n-1} dp[i] \]

对 "abbccc" 计算：
dp: [1,1,2,1,2,3]
sum = 1+1+2+1+2+3 = 10。

6. 算法步骤

1. 初始化 dp[0] = 1，total = 1。
2. 遍历 i 从 1 到 n-1：
   • 若 s[i] == s[i-1]，则 dp[i] = dp[i-1] + 1
   • 否则 dp[i] = 1
   • total += dp[i]
3. 返回 total % MOD。

7. 空间优化

因为 dp[i] 只依赖于 dp[i-1]，可以用一个变量 cur_len 代替数组：

• 遍历字符串，维护当前连续相同字符的长度 curLen
• 遇到相同字符，curLen++，否则 curLen = 1
• 每次将 curLen 加到答案

8. 代码示例（Python）

def countHomogenous(s: str) -> int:
    MOD = 10**9 + 7
    total = 0
    cur_len = 0
    for i, ch in enumerate(s):
        if i == 0 or ch == s[i-1]:
            cur_len += 1
        else:
            cur_len = 1
        total = (total + cur_len) % MOD
    return total

# 测试
print(countHomogenous("abbccc"))  # 输出 10

9. 复杂度分析

• 时间复杂度：\(O(n)\)，一次遍历。
• 空间复杂度：\(O(1)\)。

10. 总结

本题本质是统计所有连续相同字符的段，并对每段计算其子串数之和。
动态规划思路简洁：dp[i] 表示以 i 结尾的连续相同字符的长度，最终答案是所有 dp[i] 之和。
通过空间优化，可以在常数空间内完成计算。