题目描述

题目链接：3090. 每个字符最多出现两次的最长子字符串

难度：简单

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

示例 1：

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

示例 2：

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

思路1：滑动窗口

核心思想

维护窗口 [left, i]，保证窗口内每个字符最多出现 2 次：

  • 右指针 i 扩张窗口，新字符计数 +1
  • 若该字符计数超过 2，左指针 left 右移收缩，直到恢复合法
  • 每轮用当前窗口长度更新答案

为什么只需检查新加入的字符？ 加入之前窗口是合法的，超标只可能是新字符自己造成的。

为什么滑动窗口不会漏解？ 窗口字符变多只会让”出现次数超标”更容易发生，左指针只需单调右移、永不回退，因此每个右端点 i 对应的最长合法窗口都能被找到。

手动模拟（示例 1）

s = "bcbbbcba"：

i 字符 收缩过程 窗口 ans
0 b — b 1
1 c — bc 2
2 b — bcb 3
3 b 弹出s[0]='b'，left=1 cbb 3
4 b 弹出s[1]='c'，left=2，仍超标；再弹出 s[2]='b'，left=3 bb 3
5 c — bbc 3
6 b 弹出s[3]='b'，left=4 bcb 3
7 a — bcba 4

复杂度

  • 时间复杂度 ：left 和 i 均单调右移，每个字符最多进出窗口各一次
  • 空间复杂度 ：cnt 数组固定 26 个元素，与输入规模无关

代码

class Solution {
public:
    int maximumLengthSubstring(string s) {
        int ans = 0, left = 0, cnt[26]{};

        for (int i = 0; i < s.length(); ++i) {
            int b = s[i] - 'a';
            cnt[b]++;                   // 右指针扩张：新字符入窗

            while (cnt[b] > 2) {        // 只需检查新字符 b，其他字符必然合法
                cnt[s[left] - 'a']--;   // 先减计数
                left++;                 // 再移左指针
            }

            ans = max(ans, i - left + 1);  // 此时窗口必合法，更新答案
        }

        return ans;
    }
};

易错点

  • 收缩顺序：while 循环内必须先 cnt[s[left] - 'a']-- 再 left++，顺序颠倒会减错字符
  • 数组代替哈希表的前提：题目限定只有小写字母；若字符集更大（如 ASCII 全字符）需开 cnt[128] 或改用 unordered_map
  • 模板泛化：把 cnt[b] &gt; 2 换成 &gt; k，即为”每个字符最多出现 k 次”的通解

相似题目

参考