统计同构子字符串的数量 题目描述 给定一个长度为 n 的字符串 s，统计其中同构子字符串的数量。同构子字符串定义为：子字符串中的所有字符都相同。注意，单个字符也视为同构子字符串。例如，在字符串 "aaabb" 中，同构子字符串包括 "a"、"a"、"a"、"b"、"b"、"aa"、"aa"、"aaa"、"bb"，总数为 9。 解题过程 我们需要统计所有可能的连续相同字符组成的子串数量，这里采用线性动态规划的思考方式，逐步推导。 1. 问题分析 对于字符串 s 的每个位置 i，我们可以考虑以 s[ i] 结尾的同构子字符串的数量。如果 s[ i] 与 s[ i-1] 相同，那么以 s[ i] 结尾的同构子字符串可以从以 s[ i-1] 结尾的那些子字符串延伸而来，并加上一个新的只包含 s[ i] 的子字符串。如果 s[ i] 与 s[ i-1] 不同，那么只能以 s[ i ] 自己作为一个新的同构子字符串。 2. 定义状态 设 dp[ i ] 表示以第 i 个字符结尾的同构子字符串的数量。这里 i 从 0 开始索引。 3. 状态转移方程 如果 i = 0（即第一个字符），那么 dp[ 0 ] = 1，因为只有一个字符的子串。 如果 i > 0： 如果 s[ i] == s[ i-1]，则 dp[ i] = dp[ i-1 ] + 1。 解释：以 s[ i ] 结尾的同构子字符串包括： （1）所有以 s[ i-1] 结尾的同构子字符串末尾添上 s[ i]（共 dp[ i-1 ] 个）； （2）新的只包含 s[ i ] 的子字符串（长度为 1 的单个字符子串）。 如果 s[ i] != s[ i-1]，则 dp[ i ] = 1。 解释：只能形成一个新的以 s[ i ] 结尾的同构子字符串（即它自己）。 4. 求解目标 我们需要统计所有位置 i 的 dp[ i ] 之和，即总同构子字符串数量。 因此，目标为：sum(dp[ i ]) for i in 0..n-1。 5. 示例推导 以 s = "aaabb" 为例，n = 5。 i=0, s[ 0]='a'，dp[ 0 ]=1，累加和=1。 i=1, s[ 1]='a'，等于前一个字符，dp[ 1]=dp[ 0 ]+1=1+1=2，累加和=1+2=3。 （这里的2对应："a"（从s[ 0 ]延伸）、"aa"） i=2, s[ 2]='a'，等于前一个字符，dp[ 2]=dp[ 1 ]+1=2+1=3，累加和=3+3=6。 （新增："a"（从s[ 1 ]延伸）、"aa"、"aaa"） i=3, s[ 3]='b'，不等于前一个字符，dp[ 3 ]=1，累加和=6+1=7。 （新增："b"） i=4, s[ 4]='b'，等于前一个字符，dp[ 4]=dp[ 3 ]+1=1+1=2，累加和=7+2=9。 （新增："b"（从s[ 3 ]延伸）、"bb"） 最终结果为 9，与例子一致。 6. 代码实现要点 我们可以简化 dp 数组，只用一个变量 prev 记录前一个 dp 值，和一个变量 total 累加结果。 初始化 prev = 0, total = 0。 遍历 i 从 0 到 n-1： 如果 i==0 或 s[ i] != s[ i-1 ]，则 cur = 1。 否则 cur = prev + 1。 累加 total += cur。 更新 prev = cur。 最后 total 即为答案。 7. 时间复杂度与空间复杂度 时间复杂度：O(n)，只需要一次遍历。 空间复杂度：O(1)，只用了常数变量。 8. 进一步思考 这个问题的本质是：对于每个连续相同字符的段，假设其长度为 L，那么这一段贡献的同构子字符串数量为 1 + 2 + ... + L = L* (L+1)/2。我们可以扫描统计每个连续段的长度，直接加和每个段的贡献，结果一致。动态规划方法提供了一种递推的思路，更容易扩展到更复杂的情形（如统计满足某些条件的连续子串数量）。