区间动态规划例题：统计同构子字符串的数目问题（字符替换成本版本）

题目描述

给定一个字符串s和一个整数数组cost，其中cost[i]表示将字符s[i]替换为任意其他字符的成本。我们可以执行任意次替换操作，每次操作的成本为cost[i]。

定义同构子字符串：如果一个字符串的所有字符都相同，则称该字符串为同构字符串。

请计算通过执行替换操作（总成本不超过预算B）后，字符串s中可能的最长同构子字符串的长度。

解题过程

这个问题结合了区间动态规划和二分查找的思想。我们需要找到在成本限制下能够获得的最长同构子串。

步骤1：问题分析

• 目标：在预算B内，通过替换某些字符，使得字符串中出现尽可能长的连续相同字符段
• 约束：总替换成本不能超过B
• 关键观察：最优解一定是将某个区间内的字符全部替换为同一个字符

步骤2：动态规划状态定义
定义dp[i][j]表示将子串s[i...j]变为同构字符串的最小成本。

由于我们需要处理任意字符替换，状态需要记录目标字符：
dp[i][j][c] = 将s[i...j]全部变为字符c的最小成本

但这样状态空间太大（O(n²×26)），需要寻找更高效的方法。

步骤3：优化状态设计
观察发现，对于任意区间[i,j]，最优解一定是全部变为某个出现在该区间中的字符（因为如果目标字符不在区间中出现，成本可能更高）。

我们可以定义：
dp[i][j] = 将s[i...j]变为同构字符串的最小成本

状态转移：

1. 如果s[i] == s[j]，那么dp[i][j] = dp[i+1][j-1] + 替换中间字符的成本
2. 否则，dp[i][j] = min(dp[i+1][j] + cost[i], dp[i][j-1] + cost[j])

步骤4：更优的解法——滑动窗口+前缀和
实际上，这个问题有更高效的O(n)解法：

对于每个可能的字符c，我们计算将某个区间内所有非c字符替换为c的成本，找到在预算B内的最长区间。

具体算法：

1. 对于每个字符c（26种可能）
2. 使用滑动窗口，维护窗口内将非c字符替换为c的总成本
3. 当成本超过B时，移动左指针
4. 记录最大窗口长度

步骤5：滑动窗口实现细节

def longestHomogeneousSubstring(s: str, cost: List[int], B: int) -> int:
    max_len = 0
    n = len(s)
    
    for target_char in set(s):  # 遍历所有可能的目标字符
        left = 0
        current_cost = 0
        
        for right in range(n):
            # 如果当前字符不是目标字符，需要替换
            if s[right] != target_char:
                current_cost += cost[right]
            
            # 如果成本超预算，移动左指针
            while current_cost > B and left <= right:
                if s[left] != target_char:
                    current_cost -= cost[left]
                left += 1
            
            # 更新最大长度
            max_len = max(max_len, right - left + 1)
    
    return max_len

步骤6：复杂度分析

• 时间复杂度：O(26×n) = O(n)，其中26是字符集大小
• 空间复杂度：O(1)，只使用了常数个变量

步骤7：边界情况处理

• 空字符串：返回0
• 预算B=0：只能使用原本就是同构的子串
• 所有cost[i]=0：可以任意替换，答案为整个字符串长度

步骤8：示例验证
例：s = "aabaa", cost = [1,1,3,2,1], B = 2

• 目标字符'a'：最长有效区间[0,4]，成本=3（替换索引2的'b'），但成本超预算
• 调整后得到区间[0,3]，长度=4
• 最终答案：4

这种方法确保了在O(n)时间内找到最优解，比传统的区间DP更高效。