线性动态规划：统计只含单一字母的最长子串

题目描述
给定一个字符串s，你需要找到其中最长的子串，该子串中的所有字符都相同。但是，你最多可以进行k次字符替换操作，每次操作可以将任意位置的字符替换成任意其他字符。请计算在最多进行k次替换后，能够得到的只含单一字母的最长子串的长度。

解题过程

这个问题可以通过滑动窗口结合动态规划思想来解决。让我详细解释每一步：

1. 问题分析

• 我们需要找到一个子串，经过最多k次字符替换后，这个子串中的所有字符都变成相同的
• 等价于：找到一个子串，其中出现次数最多的字符的次数加上k不小于子串长度
• 即：子串长度 - 该子串中出现次数最多的字符的次数 ≤ k

2. 核心思路
使用滑动窗口方法，维护一个窗口[l, r]，保证窗口内的子串满足替换条件：

• 窗口内出现次数最多的字符的次数 + k ≥ 窗口长度

3. 具体步骤

步骤1：变量定义

def longest_substring(s: str, k: int) -> int:
    n = len(s)
    max_length = 0  # 记录最长子串长度
    left = 0  # 滑动窗口左边界
    char_count = {}  # 记录窗口内各字符出现次数
    max_freq = 0  # 记录窗口内出现最多次数字符的频率

步骤2：滑动窗口遍历

for right in range(n):  # 右边界从0到n-1遍历
    # 更新当前字符计数
    char_count[s[right]] = char_count.get(s[right], 0) + 1
    # 更新窗口内最大频率
    max_freq = max(max_freq, char_count[s[right]])

步骤3：检查窗口有效性

    # 如果当前窗口不满足条件：窗口长度 - 最大频率 > k
    while (right - left + 1) - max_freq > k:
        # 移动左边界，缩小窗口
        char_count[s[left]] -= 1
        left += 1
        # 重新计算最大频率
        max_freq = max(char_count.values()) if char_count else 0

步骤4：更新结果

    # 更新最长子串长度
    max_length = max(max_length, right - left + 1)

4. 完整代码实现

def longest_substring(s: str, k: int) -> int:
    n = len(s)
    if n == 0:
        return 0
    
    max_length = 0
    left = 0
    char_count = {}
    max_freq = 0
    
    for right in range(n):
        # 更新右边界字符计数
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        max_freq = max(max_freq, char_count[s[right]])
        
        # 检查窗口是否有效
        while (right - left + 1) - max_freq > k:
            char_count[s[left]] -= 1
            left += 1
            # 重新计算最大频率
            max_freq = max(char_count.values())
        
        # 更新结果
        max_length = max(max_length, right - left + 1)
    
    return max_length

5. 算法分析

• 时间复杂度：O(n)，每个字符最多被访问两次（右指针一次，左指针一次）
• 空间复杂度：O(字符集大小)，这里最多是O(26)

6. 示例演示
以s = "AABABBA", k = 1为例：

• 初始：left=0, max_length=0
• right=0: 窗口"A"，max_freq=1，有效，max_length=1
• right=1: 窗口"AA"，max_freq=2，有效，max_length=2
• right=2: 窗口"AAB"，max_freq=2，替换1次有效，max_length=3
• right=3: 窗口"AABA"，max_freq=3，替换1次有效，max_length=4
• right=4: 窗口"AABAB"，需要移动左边界...
• 最终得到最长子串长度为4

这个算法巧妙地利用了滑动窗口和频率统计，高效地解决了问题。