3090. 每个字符最多出现两次的最长子字符串

🎯 问题描述（来源于LeetCode）

描述：
给你一个字符串 s，请找出满足每个字符最多出现两次的最长子字符串，并返回该子字符串的最大长度。

说明：

子字符串：字符串中一段连续非空的字符序列。
核心逻辑：使用滑动窗口维护一个“每个字符出现次数不超过 2 次”的区间。当某个字符出现次数达到 3 次时，收缩左边界，直到该字符次数恢复为 2 次。
示例：
示例 1：

输入： s = "bcbbbcba"
输出： 4
解释：
以下子字符串长度为 4，并且每个字符最多出现两次：`"bcbbbcba"`。

示例 2：

输入：s = "aaaa"
输出：2
解释：
子字符串 "aa" 满足条件（'a' 出现 2 次）。
子字符串 "aaa" 不满足条件（'a' 出现 3 次）。

💻 解题思路

思路1：不定长滑动窗口

思路1：代码实现

class Solution:
    def maximumLengthSubstring(self, s: str) -> int:
        ans = 0             # 记录满足条件的最长子字符串长度
        cnt = Counter()     # 哈希表，记录窗口内每个字符出现的次数
        left = 0            # 窗口左边界
        
        # 右边界 right 随循环遍历字符串
        for right, c in enumerate(s):
            # 1. 扩展窗口：将当前字符加入哈希表
            cnt[c] += 1
            
            # 2. 收缩窗口：如果当前字符出现次数超过 2
            # 则不断移动左边界，直到当前字符次数恢复为 2 或更少
            while cnt[c] > 2:
                cnt[s[left]] -= 1
                left += 1
            
            # 3. 更新答案：此时窗口 [left, right] 内所有字符出现次数 <= 2
            ans = max(ans, right - left + 1)
            
        return ans

思路1：📊 性能分析

时间复杂度： $O(N)$ $O (N)$
- 其中 $N$ 是字符串 s 的长度。
- 虽然代码中有一个 while 循环嵌套在 for 循环中，但每个字符最多被访问两次（一次被右边界 right 加入，一次被左边界 left 移出）。因此，整体操作次数是线性的。
空间复杂度： $O(1)$ $O (1)$
- 哈希表 cnt 最多存储 26 个小写英文字母的计数，这是一个常数空间。

思考

**与无重复字符的最长子串**的区别：
- 无重复字符的最长子串要求每个字符出现次数 $\le 1$ 。
- 本题要求每个字符出现次数 $\le 2$ 。
- 代码逻辑几乎完全相同，只是将判断条件从 cnt[c] > 1 改为了 cnt[c] > 2。
滑动窗口的通用性：
- 这种不定长滑动窗口的模板非常通用，可以解决很多“满足某种条件的最长/最短子数组/子串”问题。
- 核心在于维护一个合法的窗口，并在窗口不合法时收缩左边界。
答案更新：
- ans = max(ans, right - left + 1) 放在 while 循环之后，确保只在窗口合法时更新答案。
- 此时窗口 [left, right] 内的所有字符出现次数都不超过 2 次，满足题目要求。