统计只含单一字符的最长子串

我将为你讲解一个线性动态规划领域的经典问题：统计只含单一字符的最长子串。这是一个基础但非常重要的题目，能帮助你理解如何用动态规划处理字符串中连续相同字符的统计问题。

问题描述

给定一个字符串 s，统计其中只包含单一字符（即所有字符都相同）的最长子串的长度。例如：

• 输入: "aaabbbccdd"，输出: 3（因为子串 "aaa" 或 "bbb" 的长度为3）。
• 输入: "abcde"，输出: 1（每个字符单独形成一个长度为1的单一字符子串）。

这个问题是许多更复杂问题的基础，比如“最多允许替换k次字符的最长子串”等。

解题思路

我们可以用一个简单直观的线性动态规划来解决这个问题。基本思路是遍历字符串，用一个状态记录“以当前字符结尾的、只包含单一字符的子串的长度”。然后，在遍历过程中更新全局的最大长度。

状态定义

定义 dp[i] 表示以字符串中第 i 个字符（索引从0开始）结尾的、只包含单一字符的子串的最大长度。

状态转移方程

• 如果 s[i] == s[i-1]，即当前字符和前一个字符相同，那么以当前字符结尾的单一字符子串可以继续延长，所以 dp[i] = dp[i-1] + 1。
• 如果 s[i] != s[i-1]，即当前字符和前一个字符不同，那么以当前字符结尾的单一字符子串只能从当前字符重新开始，所以 dp[i] = 1。

用数学公式表示：

\[dp[i] = \begin{cases} dp[i-1] + 1, & \text{if } s[i] = s[i-1] \\ 1, & \text{if } s[i] \neq s[i-1] \end{cases} \]

初始化

• 对于第一个字符（i = 0），以它结尾的单一字符子串长度显然是1，所以 dp[0] = 1。

计算顺序

从 i = 1 开始，从左到右遍历字符串，根据状态转移方程计算每个 dp[i]，同时用一个变量 max_len 记录所有 dp[i] 中的最大值。

最终结果

遍历结束后，max_len 就是整个字符串中最长的单一字符子串的长度。

详细步骤

让我们用示例 s = "aaabbbccdd" 来走一遍过程。

1. 初始化

   • 创建一个长度与 s 相同的数组 dp，dp[0] = 1。
   • max_len = 1。

2. 遍历字符串（i 从1到9）：

   • i=1: s[1]='a'，s[0]='a'，相同 → dp[1] = dp[0] + 1 = 2，max_len = max(1, 2) = 2。
   • i=2: s[2]='a'，s[1]='a'，相同 → dp[2] = dp[1] + 1 = 3，max_len = max(2, 3) = 3。
   • i=3: s[3]='b'，s[2]='a'，不同 → dp[3] = 1，max_len 保持3。
   • i=4: s[4]='b'，s[3]='b'，相同 → dp[4] = dp[3] + 1 = 2，max_len 保持3。
   • i=5: s[5]='b'，s[4]='b'，相同 → dp[5] = dp[4] + 1 = 3，max_len 保持3。
   • i=6: s[6]='c'，s[5]='b'，不同 → dp[6] = 1，max_len 保持3。
   • i=7: s[7]='c'，s[6]='c'，相同 → dp[7] = dp[6] + 1 = 2，max_len 保持3。
   • i=8: s[8]='d'，s[7]='c'，不同 → dp[8] = 1，max_len 保持3。
   • i=9: s[9]='d'，s[8]='d'，相同 → dp[9] = dp[8] + 1 = 2，max_len 保持3。

3. 结果：max_len = 3。

这样，我们得到了最长单一字符子串的长度为3。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串长度，我们只遍历了一次字符串。
• 空间复杂度：O(n)，用于存储 dp 数组。实际上，由于我们只需要前一个状态，可以优化到 O(1)，只需要一个变量来记录前一个 dp 值，以及一个变量记录全局最大值。

代码实现（Python）

def longest_single_character_substring(s: str) -> int:
    if not s:
        return 0
    
    n = len(s)
    dp = [0] * n
    dp[0] = 1
    max_len = 1
    
    for i in range(1, n):
        if s[i] == s[i-1]:
            dp[i] = dp[i-1] + 1
        else:
            dp[i] = 1
        max_len = max(max_len, dp[i])
    
    return max_len

空间优化版本：

def longest_single_character_substring_optimized(s: str) -> int:
    if not s:
        return 0
    
    prev_len = 1
    max_len = 1
    
    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            curr_len = prev_len + 1
        else:
            curr_len = 1
        max_len = max(max_len, curr_len)
        prev_len = curr_len
    
    return max_len

扩展思考

这个问题是许多变种问题的基础，比如：

1. 允许最多替换k次字符的最长子串：在一个字符串中，你可以替换最多k个字符，使得替换后整个子串变为单一字符，求最长的子串长度。这可以用滑动窗口解决。
2. 统计所有单一字符子串的个数：可以修改状态定义，计算以每个位置结尾的单一字符子串个数，然后求和。

通过这个基础问题，你可以更好地理解动态规划在处理连续子串问题中的应用。希望这个讲解能帮助你！