解决最长无重复子串问题

在编程面试中，字符串处理常常是考察算法能力的重要部分。今天，我们将探讨一个经典问题——最长无重复子串问题，并给出 Python 代码实现。

问题描述

给定一个字符串 s，你需要找到其中最长的无重复字符的子串，并返回它的长度。

例如：

• 输入：s = "abcabcbb"
• 输出：3，因为 "abc" 是最长的无重复字符子串，长度为 3。

解题思路

解决这个问题的常见方法是使用滑动窗口技术。在这种方法中，我们通过维护一个窗口来跟踪当前的子串，并且使用一个哈希表来快速判断当前子串中是否有重复字符。

具体步骤如下：

1. 滑动窗口：我们使用两个指针来定义一个窗口，窗口的左边指针 left 和右边指针 right。右边指针向右扩展，尝试通过不断增加新的字符来扩展窗口。当遇到重复字符时，左边指针将被移动，从而缩小窗口，直到窗口内没有重复字符为止。

2. 哈希表：我们使用一个哈希表 str_dict 来记录每个字符上次出现的位置。如果遇到重复字符，就可以通过哈希表直接找到重复字符上次出现的位置，并更新左边指针的位置。

3. 最大长度：在每次扩展窗口时，我们记录当前窗口的长度 index - left + 1，并更新最长的无重复子串的长度。

代码实现

下面是这个算法的 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"

处理过程：

1. 第一个字符 'a'，没有重复，max_len = 1。
2. 第二个字符 'b'，没有重复，max_len = 2。
3. 第三个字符 'c'，没有重复，max_len = 3。
4. 第四个字符 'a'，重复，更新 left = 1，max_len 不变。
5. 第五个字符 'b'，重复，更新 left = 2，max_len 不变。
6. 第六个字符 'c'，重复，更新 left = 3，max_len 不变。
7. 第七个字符 'b'，重复，更新 left = 4，max_len 不变。
8. 第八个字符 'b'，重复，更新 left = 5，max_len 不变。

最终返回值是 3，最长无重复子串为 "abc"。

示例 2

输入：

s = "bbbbb"

处理过程：

1. 第一个字符 'b'，没有重复，max_len = 1。
2. 第二个字符 'b'，重复，更新 left = 1，max_len 不变。
3. 第三个字符 'b'，重复，更新 left = 2，max_len 不变。
4. 第四个字符 'b'，重复，更新 left = 3，max_len 不变。
5. 第五个字符 'b'，重复，更新 left = 4，max_len 不变。

最终返回值是 1，最长无重复子串为 "b"。

示例 3

输入：

s = "pwwkew"

处理过程：

1. 第一个字符 'p'，没有重复，max_len = 1。
2. 第二个字符 'w'，没有重复，max_len = 2。
3. 第三个字符 'w'，重复，更新 left = 2，max_len 不变。
4. 第四个字符 'k'，没有重复，max_len = 3。
5. 第五个字符 'e'，没有重复，max_len = 4。
6. 第六个字符 'w'，重复，更新 left = 4，max_len 不变。

最终返回值是 3，最长无重复子串为 "wke"。

时间复杂度与空间复杂度

时间复杂度

• 遍历字符串需要 O(n) 的时间，其中 n 是字符串的长度。
• 每次查找和更新哈希表的操作是常数时间 O(1)。 因此，总的时间复杂度是 O(n)。

空间复杂度

• 哈希表 str_dict 最多存储 O(n) 个字符。 因此，空间复杂度是 O(n)。

总结

本题通过滑动窗口的方式解决了最长无重复子串的问题。这种方法不仅高效，而且直观。掌握滑动窗口技术在解决类似问题时十分有用，尤其是处理字符串、数组等线性数据结构时。希望这篇文章能帮助你更好地理解并实现这个经典问题！