0003. Longest Substring Without Repeating Characters ==================================================== 题目信息 -------- :题号: 0003. 无重复字符的最长子串 :难度: Medium :主题: 字符串、滑动窗口、哈希表 :原题: `LeetCode 0003 `_ :重点: 从重复检查连续子串,推导到维护无重复窗口,再利用字符最近位置直接跳过失效前缀 题目重述 -------- 给定字符串 ``s``,需要返回其中不含重复字符的最长连续子串长度。子串必须对应原字符串中的一段连续区间,不能跳过字符重新组合;若存在多个等长答案,只返回长度。 字符串长度位于 ``[0, 5 * 10^4]``,其中可能包含英文字母、数字、符号和空格。空格与标点同样属于字符,参与重复判断;空字符串的答案为 ``0``。 自建示例 -------- * 普通重复:``s = "abcabcbb"``,最长无重复子串可以是 ``"abc"``,返回 ``3``; * 最优区间位于中部:``s = "abcbadeaf"``,最长无重复子串为 ``"cbade"``,返回 ``5``; * 重复字符连续出现:``s = "bbbbb"``,任意合法子串都只能包含一个 ``b``,返回 ``1``; * 空格和符号:``s = "a b!a"``,``"a b!"`` 与 ``" b!a"`` 的长度都为 ``4``,返回 ``4``; * 空字符串:``s = ""``,返回 ``0``。 C++ 实现 -------- .. code-block:: cpp #include #include #include class Solution { private: int enumerateStarts(const std::string& s) { int best = 0; for (int left = 0; left < static_cast(s.size()); ++left) { std::array used{}; for (int right = left; right < static_cast(s.size()); ++right) { const auto ch = static_cast(s[right]); if (used[ch]) { break; } used[ch] = true; best = std::max(best, right - left + 1); } } return best; } int shrinkWithSet(const std::string& s) { std::array inWindow{}; int left = 0; int best = 0; for (int right = 0; right < static_cast(s.size()); ++right) { const auto ch = static_cast(s[right]); while (inWindow[ch]) { const auto removed = static_cast(s[left]); inWindow[removed] = false; ++left; } inWindow[ch] = true; best = std::max(best, right - left + 1); } return best; } int jumpWithLastPosition(const std::string& s) { std::array last; last.fill(-1); int left = 0; int best = 0; for (int right = 0; right < static_cast(s.size()); ++right) { const auto ch = static_cast(s[right]); left = std::max(left, last[ch] + 1); last[ch] = right; best = std::max(best, right - left + 1); } return best; } public: int lengthOfLongestSubstring(std::string s) { return jumpWithLastPosition(s); } }; 题解 ---- 原始搜索空间 ~~~~~~~~~~~~ 长度为 ``n`` 的字符串共有 ``n(n + 1) / 2`` 个非空连续子串。最直接的方法是固定左端点 ``left``,再不断扩展右端点 ``right``,使用字符表检查当前区间是否出现重复。 ``enumerateStarts`` 为每个新左端点重新建立 ``used``。一旦遇到重复字符,继续扩大右端点只会保留已经存在的冲突,因此当前内层循环可以立即停止。 这个剪枝避免了检查同一左端点下更长的非法区间,但相邻左端点之间仍会重复扫描大量相同字符。最坏情况下,例如字符串中的字符长期不重复,每个左端点都可能一直扫描到末尾,总时间仍为 ``O(n²)``。 窗口状态复用 ~~~~~~~~~~~~ 右端点从左向右移动时,相邻候选区间通常共享大部分字符。重新为每个左端点检查整个区间,丢弃了这些已经确认的信息。 可以维护一个始终无重复的窗口 ``[left, right]``: * ``right`` 每轮加入一个新字符; * 若新字符与窗口内旧字符重复,右移 ``left``,删除失效前缀; * 窗口重新合法后,用 ``right - left + 1`` 更新答案。 加入新字符之前,旧窗口已经无重复,所以本轮唯一可能新增的冲突只来自 ``s[right]``。算法不需要重新检查窗口中其他字符之间的关系。 字符集合窗口 ~~~~~~~~~~~~ ``shrinkWithSet`` 使用 ``inWindow`` 记录字符是否位于当前窗口中。若当前字符已经存在,就从窗口左端逐个移除字符,直到旧的同字符也被删除,再把当前字符加入窗口。 这一版已经把时间复杂度降为 ``O(n)``。右端点只前进 ``n`` 次,每个字符也最多被左端移出一次,所以两个指针的总移动次数为线性数量级。 集合只保存“是否存在”,不知道旧字符的具体位置。因此发生重复时,代码必须通过 ``while`` 循环逐个删除失效前缀。下一步优化不是改变渐进复杂度,而是让状态直接指出左边界应跳到哪里。 最近位置跳跃 ~~~~~~~~~~~~ ``jumpWithLastPosition`` 使用 ``last[ch]`` 保存字符 ``ch`` 在已扫描前缀中的最近下标。处理 ``right`` 处字符时,设其旧位置为 ``p``: * 若 ``p < left``,旧字符已经位于窗口外,不会产生冲突; * 若 ``p >= left``,窗口同时包含旧字符和当前字符,左边界必须移动到 ``p + 1``; * 两种情况统一为 ``left = max(left, p + 1)``。 这里的 ``max`` 不能省略。左边界只能保持或右移,不能因为当前字符更早的一次出现而退回,否则会重新包含之前已经排除的重复字符。 更新左边界后再执行 ``last[ch] = right``,让当前位置成为后续扫描使用的最近位置。字符集合方案中的逐个删除循环因此消失,恢复窗口合法性只需一次边界更新。 状态推演 ~~~~~~~~ 以 ``s = "abcbadeaf"`` 为例: .. list-table:: :header-rows: 1 * - ``right`` - 字符 - 旧位置 - 原 ``left`` - 新 ``left`` - 当前窗口 - ``best`` * - 0 - ``a`` - -1 - 0 - 0 - ``a`` - 1 * - 1 - ``b`` - -1 - 0 - 0 - ``ab`` - 2 * - 2 - ``c`` - -1 - 0 - 0 - ``abc`` - 3 * - 3 - ``b`` - 1 - 0 - 2 - ``cb`` - 3 * - 4 - ``a`` - 0 - 2 - 2 - ``cba`` - 3 * - 5 - ``d`` - -1 - 2 - 2 - ``cbad`` - 4 * - 6 - ``e`` - -1 - 2 - 2 - ``cbade`` - 5 * - 7 - ``a`` - 4 - 2 - 5 - ``dea`` - 5 * - 8 - ``f`` - -1 - 5 - 5 - ``deaf`` - 5 处理下标 ``4`` 的 ``a`` 时,它的旧位置 ``0`` 已经位于窗口左侧,因此 ``left`` 保持为 ``2``。处理下标 ``7`` 的 ``a`` 时,旧位置 ``4`` 位于当前窗口内,左边界直接跳到 ``5``。 代码演进 ~~~~~~~~ ``enumerateStarts`` 使用两层循环:外层选择左端点,内层重新检查该起点能够扩展多远。瓶颈来自不同起点之间反复扫描相同字符。 ``shrinkWithSet`` 保留上一个窗口的字符状态,外层左端枚举消失,改为两个只向右移动的边界。重复出现时仍需要逐个删除窗口前缀,因为布尔表只知道字符是否存在。 ``jumpWithLastPosition`` 把布尔状态升级为最近下标。``while`` 删除循环和逐字符清理操作消失,左边界可以一次跳到旧字符之后。 三种实现对应三层认识: * 不复用区间信息时,为每个左端点重新扩展; * 维护合法窗口时,每个字符最多进入和离开窗口一次; * 保存最近位置时,可以直接计算新的最小合法左边界。 公开入口采用 ``jumpWithLastPosition``。它保持 ``O(n)`` 时间,同时避免集合窗口发生冲突时的逐步删除操作。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要代价 * - 固定左端扩展 - ``O(n²)`` - ``O(1)`` - 为每个左端点重新扫描后续字符 * - 字符集合窗口 - ``O(n)`` - ``O(1)`` - 每个字符最多进入和移出窗口一次 * - 最近位置跳跃 - ``O(n)`` - ``O(1)`` - 每个字符执行一次位置读取与写入 题目字符可以按单字节字符处理,因此固定的 256 项数组记为 ``O(1)`` 工作空间。若推广到更大的字符域并改用哈希表,空间复杂度为 ``O(k)``,其中 ``k`` 是记录过的不同字符数量。 边界处理 ~~~~~~~~ * 空字符串不会进入循环,初始答案 ``0`` 直接返回; * 全部字符相同时,窗口每轮只保留当前字符,答案为 ``1``; * 空格、数字和标点都通过同一字符索引参与重复判断; * 使用 ``unsigned char`` 转换后再作为数组下标,避免有符号 ``char`` 产生负下标; * 左边界通过 ``max`` 保证只向右移动,不会重新引入已经排除的重复字符。