在编程面试中，字符串处理常常是考察算法能力的重要部分。今天，我们将探讨一个经典问题——最长无重复子串问题，并给出 Python 代码实现。
问题描述
给定一个字符串 s，你需要找到其中最长的无重复字符的子串，并返回它的长度。
例如：
- 输入：
s = "abcabcbb" - 输出：
3，因为 "abc" 是最长的无重复字符子串，长度为 3。
解题思路
解决这个问题的常见方法是使用滑动窗口技术。在这种方法中，我们通过维护一个窗口来跟踪当前的子串，并且使用一个哈希表来快速判断当前子串中是否有重复字符。
具体步骤如下：
-
滑动窗口：我们使用两个指针来定义一个窗口，窗口的左边指针
left和右边指针right。右边指针向右扩展，尝试通过不断增加新的字符来扩展窗口。当遇到重复字符时，左边指针将被移动，从而缩小窗口，直到窗口内没有重复字符为止。 -
哈希表：我们使用一个哈希表
str_dict来记录每个字符上次出现的位置。如果遇到重复字符，就可以通过哈希表直接找到重复字符上次出现的位置，并更新左边指针的位置。 -
最大长度：在每次扩展窗口时，我们记录当前窗口的长度
index - left + 1，并更新最长的无重复子串的长度。
代码实现
下面是这个算法的 Python 实现：
python">class Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""max_len = 0 # 用来保存最长无重复子串的长度str_dict = {} # 用来存储每个字符最后一次出现的索引left = 0 # 滑动窗口的左指针# 遍历字符串for index, char in enumerate(s):# 如果当前字符在 str_dict 中且位置大于等于 left，说明有重复字符if char in str_dict and str_dict[char] >= left:# 更新左指针，跳过重复字符left = str_dict[char] + 1# 更新字符的最新位置str_dict[char] = index# 计算当前窗口的长度并更新最大长度max_len = max(max_len, index - left + 1)return max_len
代码解析
1. 初始化
max_len：用来存储当前找到的最长无重复子串的长度，初始化为 0。str_dict：这是一个字典，记录每个字符的最新索引。这样可以快速查找字符是否重复以及其位置。left：滑动窗口的左指针，初始化为 0。
2. 遍历字符串
我们通过 enumerate(s) 来遍历字符串 s，index 是当前字符的索引，char 是当前字符。
-
重复字符处理：如果字符
char已经在str_dict中，并且它的最后出现位置str_dict[char]大于等于当前的left指针，那么说明当前字符是重复的。此时，更新left指针为重复字符位置的下一个位置，即left = str_dict[char] + 1。 -
更新哈希表：无论是否有重复字符，我们都会更新当前字符的最新位置，即
str_dict[char] = index。 -
计算当前窗口的长度：通过
index - left + 1计算当前窗口的长度，并更新max_len，保持最大值。
3. 返回结果
在循环结束后，max_len 就是最长无重复子串的长度，我们将其返回。
示例分析
示例 1
输入：
s = "abcabcbb"
处理过程：
- 第一个字符 'a'，没有重复，
max_len = 1。 - 第二个字符 'b'，没有重复，
max_len = 2。 - 第三个字符 'c'，没有重复，
max_len = 3。 - 第四个字符 'a'，重复，更新
left = 1，max_len不变。 - 第五个字符 'b'，重复，更新
left = 2，max_len不变。 - 第六个字符 'c'，重复，更新
left = 3，max_len不变。 - 第七个字符 'b'，重复，更新
left = 4，max_len不变。 - 第八个字符 'b'，重复，更新
left = 5，max_len不变。
最终返回值是 3，最长无重复子串为 "abc"。
示例 2
输入：
s = "bbbbb"
处理过程：
- 第一个字符 'b'，没有重复，
max_len = 1。 - 第二个字符 'b'，重复，更新
left = 1，max_len不变。 - 第三个字符 'b'，重复，更新
left = 2，max_len不变。 - 第四个字符 'b'，重复，更新
left = 3，max_len不变。 - 第五个字符 'b'，重复，更新
left = 4，max_len不变。
最终返回值是 1，最长无重复子串为 "b"。
示例 3
输入：
s = "pwwkew"
处理过程：
- 第一个字符 'p'，没有重复，
max_len = 1。 - 第二个字符 'w'，没有重复，
max_len = 2。 - 第三个字符 'w'，重复，更新
left = 2，max_len不变。 - 第四个字符 'k'，没有重复，
max_len = 3。 - 第五个字符 'e'，没有重复，
max_len = 4。 - 第六个字符 'w'，重复，更新
left = 4，max_len不变。
最终返回值是 3，最长无重复子串为 "wke"。
时间复杂度与空间复杂度
时间复杂度
- 遍历字符串需要
O(n)的时间，其中n是字符串的长度。 - 每次查找和更新哈希表的操作是常数时间
O(1)。 因此，总的时间复杂度是O(n)。
空间复杂度
- 哈希表
str_dict最多存储O(n)个字符。 因此，空间复杂度是O(n)。
总结
本题通过滑动窗口的方式解决了最长无重复子串的问题。这种方法不仅高效，而且直观。掌握滑动窗口技术在解决类似问题时十分有用，尤其是处理字符串、数组等线性数据结构时。希望这篇文章能帮助你更好地理解并实现这个经典问题！
