区间动态规划例题：统计同构子字符串的数目问题（进阶版） 题目描述 给定一个字符串 s ，统计其中同构子字符串的数目。同构子字符串定义为：该子字符串中所有字符都相同。例如，字符串 "aaa" 包含 6 个同构子字符串："a"（出现 3 次）、"aa"（出现 2 次）、"aaa"（出现 1 次）。注意：子字符串必须是连续的。 解题思路 问题分析 ：若直接枚举所有子字符串再判断是否同构，时间复杂度为 O(n³)，效率低下。同构子字符串的连续性质适合用区间动态规划优化。 关键观察 ：对于任意区间 [ i, j]，若其是同构子字符串，则必须满足 s[i] = s[i+1] = ... = s[j] 。因此，我们可以通过检查相邻字符是否相等来快速判断连续性。 动态规划定义 ：定义 dp[i][j] 表示子字符串 s[i:j] 是否为同构子字符串（True/False）。但直接存储布尔值会导致 O(n²) 空间，且统计数目时仍需遍历所有区间。更高效的方法是： 用单次遍历识别所有连续相同字符的区间，直接计算每个区间内的同构子字符串数目。 对于长度为 k 的连续相同字符区间，其包含的同构子字符串数目为 k*(k+1)/2 。 步骤详解 初始化 ： 令 count = 0 记录总数， current_len = 1 记录当前连续相同字符的长度。 遍历字符串 ： 从第二个字符开始（索引 1），比较当前字符 s[i] 与前一个字符 s[i-1] ： 若相等， current_len 加 1。 若不相等，说明当前连续区间结束，计算该区间的贡献值 current_len*(current_len+1)/2 ，加到 count ，并重置 current_len = 1 。 处理末尾区间 ： 遍历结束后，将最后一个连续区间的贡献值加入 count 。 示例演示 以 s = "aabbb" 为例： 遍历过程： i=1: 'a' == 'a' → current_len=2 i=2: 'b' != 'a' → 计算 "aa" 的贡献：2* 3/2=3， count=3 ，重置 current_len=1 i=3: 'b' == 'b' → current_len=2 i=4: 'b' == 'b' → current_len=3 结尾处理：计算 "bbb" 的贡献：3* 4/2=6， count=3+6=9 。 结果验证：同构子字符串包括 "a"(2次)、"aa"(1次)、"b"(3次)、"bb"(2次)、"bbb"(1次)，总计 2+1+3+2+1=9。 算法优化 时间复杂度：O(n)，仅需一次遍历。 空间复杂度：O(1)，仅需常数变量。 总结 本题通过识别连续字符区间，将问题转化为数学计算，避免了显式的动态规划表填充，既高效又简洁。核心在于利用同构子字符串的连续性特征，将统计问题转化为区间长度计算。