在计算字符串中最长不含有重复字符的子串长度时，通常采用滑动窗口方法，该方法通过维护一个窗口来动态调整子串的范围，以确保窗口内没有重复字符，从而找到最长的无重复字符子串。该方法的时间复杂度为 $O(n)$，具有较高的效率。 ### 滑动窗口方法的实现 滑动窗口方法通过两个指针（`left` 和 `right`）来表示窗口的范围，同时使用集合来存储当前窗口中的字符。当右指针向右移动时，如果当前字符不在集合中，则将其加入集合；如果已经存在，则从窗口的左侧开始移除字符，直到当前字符不再重复为止。在此过程中，不断更新最长子串的长度。 以下是实现代码： ```python class Solution: def lengthOfLongestSubstring(self, s: str) -> int: left = 0 max_length = 0 char_set = set() for right in range(len(s)): while s[right] in char_set: char_set.remove(s[left]) left += 1 char_set.add(s[right]) max_length = max(max_length, right - left + 1) return max_length if __name__ == "__main__": solution = Solution() print(solution.lengthOfLongestSubstring("abcabcbb")) # 输出 3 print(solution.lengthOfLongestSubstring("abdabbcba")) # 输出 3 print(solution.lengthOfLongestSubstring("abcadcedbb")) # 输出 5 print(solution.lengthOfLongestSubstring("abcdefg")) # 输出 7 ``` ### 方法分析 滑动窗口方法的核心在于通过动态调整窗口的范围，避免了暴力求解中重复检查相同子串的问题。相比于暴力求解 $O(n^2)$ 的时间复杂度，滑动窗口方法仅需一次遍历即可完成计算，效率显著提升。此外，通过集合的快速查找特性，可以高效判断当前字符是否重复。 ### 时间复杂度 - **时间复杂度**：$O(n)$，其中 $n$ 是字符串的长度。每个字符最多会被访问两次（一次由右指针添加，一次由左指针移除）。 - **空间复杂度**：$O(min(m, n))$，其中 $m$ 是字符集的大小（如 ASCII 字符集为 128），最坏情况下窗口中存储所有不重复字符。 ### 示例解析 1. 对于输入 `"abcabcbb"`，最长无重复字符的子串是 `"abc"`，其长度为 3。 2. 对于输入 `"pwwkew"`，最长无重复字符的子串是 `"wke"`，其长度为 3。 3. 对于输入 `"abcdefg"`，最长无重复字符的子串是 `"abcdefg"`，其长度为 7。 该方法能够正确处理各种情况，包括空字符串、单字符字符串以及所有字符均不重复的情况[^3]。