跳到主要内容

LeetCode 3. 无重复字符的最长子串

本节目标

用字符频次维护无重复窗口，在线得到最长合法子串长度。

这道题是滑动窗口解题框架的最长合法窗口母题。窗口内只要出现重复字符，就移动左边界直到重复消失。

查看原题

题意与约束​

给定字符串 s，返回不含重复字符的最长连续子串长度。答案是长度，不需要恢复具体子串；空字符串的答案为 0。

从枚举区间到维护合法窗口​

暴力做法枚举所有起点和终点，再检查每个区间是否有重复字符，时间会达到平方级。其实当右端加入一个字符后，只有这个新字符可能让原本合法的窗口失效。

因此用频次数组记录窗口中的字符数。加入右端后，若它的频次超过 1，就不断移除左端字符；循环结束时，窗口重新满足每个字符至多出现一次。此时窗口长度就是以当前右端结尾的最长合法长度。

代码实现​

两份源码都让左边界只向右移动。频次数组覆盖全部字节值，避免为每个字符重复扫描窗口；每次收缩只减少一个离开窗口的字符频次。

C++17
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        vector<int> counts(256);
        int left = 0;
        int best = 0;

        for (int right = 0; right < static_cast<int>(s.size()); right++) {
            counts[static_cast<unsigned char>(s[right])]++;
            // 收缩到窗口内不再包含重复字符。
            while (counts[static_cast<unsigned char>(s[right])] > 1) {
                counts[static_cast<unsigned char>(s[left])]--;
                left++;
            }
            best = max(best, right - left + 1);
        }
        return best;
    }
};

复杂度分析​

  • 时间复杂度：O(n)。左右边界都最多各移动 n 次。
  • 空间复杂度：O(1)。字符频次数组大小固定。

易错点​

  • 发现重复后只移动左边界一次；重复字符可能仍然留在窗口中，必须持续收缩。
  • 在收缩前更新最大长度；此时窗口可能不合法。
  • 把子串当成可跳过字符的子序列；窗口只能表示连续区间。

模式迁移​

右端扩张、违反约束就收缩的最长合法模式还可用于最多包含 k 种字符、替换至多 k 个字符后的最长重复字符子串等问题。状态从单个字符频次扩展为不同字符种类数或可替换次数，边界移动规则不变。