统计同构子字符串的数目问题（字符替换成本版本）

让我为您详细讲解这个区间动态规划问题。

问题描述

给定一个字符串s和一个二维数组cost，其中cost[i][j]表示将字符i替换为字符j的代价（i和j都是小写字母）。我们需要统计所有同构子字符串的数目，其中同构子字符串定义为可以通过零成本或有限成本替换字符使得该子字符串中所有字符都相同。

更具体地说，对于字符串s的任意子串s[i..j]，如果存在某个字符c，使得我们可以通过字符替换将s[i..j]中的所有字符都变成c，且总替换成本不超过给定的预算B，那么这个子串就是一个同构子字符串。

问题分析

这是一个典型的区间动态规划问题，我们需要：

1. 计算所有子串变成单一字符的最小成本
2. 统计满足成本约束的子串数量

解题步骤

步骤1：定义状态

定义dp[i][j][c]表示将子串s[i..j]中的所有字符都替换为字符c的最小成本，其中c是26个小写字母之一。

步骤2：状态转移方程

情况1：当i = j时（单个字符）

dp[i][i][c] = cost[s[i] - 'a'][c - 'a']

即单个字符替换为目标字符c的成本。

情况2：当i < j时
对于区间[i, j]，我们可以将其分割为[i, k]和[k+1, j]两个子区间：

dp[i][j][c] = min{ dp[i][k][c] + dp[k+1][j][c] }，其中i ≤ k < j

或者我们可以选择将整个区间统一替换为字符c：

dp[i][j][c] = sum{ cost[s[m] - 'a'][c - 'a'] }，其中i ≤ m ≤ j

取两者的最小值。

步骤3：初始化

• 单个字符的替换成本直接查表
• 多字符区间的初始值设为无穷大

步骤4：计算顺序

按照区间长度从小到大计算：

1. 长度为1的区间
2. 长度为2的区间
3. ......
4. 长度为n的区间

步骤5：统计结果

对于每个区间[i, j]，我们检查所有字符c：

如果 min{ dp[i][j][c] for all c } ≤ B
则计数加1

详细示例

假设字符串s = "ab"，预算B = 2，成本矩阵为：

cost[a->a] = 0, cost[a->b] = 1
cost[b->a] = 1, cost[b->b] = 0

步骤1：初始化单个字符

• dp[0][0]['a'] = cost['a']['a'] = 0
• dp[0][0]['b'] = cost['a']['b'] = 1
• dp[1][1]['a'] = cost['b']['a'] = 1
• dp[1][1]['b'] = cost['b']['b'] = 0

步骤2：计算长度为2的区间[0,1]
对于字符'a'：

• 分割方式1：[0,0]和[1,1]：dp[0][0]['a'] + dp[1][1]['a'] = 0 + 1 = 1
• 直接替换：cost['a']['a'] + cost['b']['a'] = 0 + 1 = 1
• dp[0][1]['a'] = min(1, 1) = 1

对于字符'b'：

• 分割方式1：[0,0]和[1,1]：dp[0][0]['b'] + dp[1][1]['b'] = 1 + 0 = 1
• 直接替换：cost['a']['b'] + cost['b']['b'] = 1 + 0 = 1
• dp[0][1]['b'] = min(1, 1) = 1

步骤3：统计结果

• 区间[0,0]：min(0,1) = 0 ≤ 2 ✓
• 区间[1,1]：min(1,0) = 0 ≤ 2 ✓
• 区间[0,1]：min(1,1) = 1 ≤ 2 ✓
  总计：3个同构子字符串

算法优化

由于需要存储26个字符的状态，空间复杂度为O(26×n²)。我们可以优化为只存储最小成本而不记录具体字符：

dp[i][j] = 将子串s[i..j]变为同构字符串的最小成本

优化后的状态转移：

dp[i][j] = min{ 
    dp[i][k] + dp[k+1][j],  // 分割方式
    min_char{ sum{cost[s[m]-'a'][c-'a']} }  // 统一替换为某个字符
}

复杂度分析

• 时间复杂度：O(n³ × 26)，其中n为字符串长度
• 空间复杂度：O(n²)

这个算法通过动态规划系统地计算了所有子串变为同构字符串的最小成本，并统计了满足预算约束的子串数量。