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

Posted on Edited on In Views: Word count in article: 1.3k Reading time ≈ 1 mins.

3 无重复字符的最长子串

题目链接：3. 无重复字符的最长子串

核心思考：如何寻找最长子串？

对于寻找“无重复字符”的最长子串，最直观的想法就是穷举：也就是暴力遍历。
尝试从每一个字符开始，向后看能走多远而不遇到重复的字符。但这会带来 $O(n^2)$ 的时间复杂度。

我们可以优化这个过程。在向后扫描的过程中，当遇到一个已经出现过的字符时，前面已经建立好的“无重复状态”被打破了。此时我们不需要重新从头再来寻找，而是可以通过滑动窗口的机制，只剔除掉造成重复的部分。

解题思路

方法一：暴力遍历 (Brute Force)

暴力的思路非常简单，使用两个嵌套循环。外部循环固定子串的起始位置，内部循环向后扩展并检查是否遇到重复字符。

局限性：这种方法时间复杂度为 $O(n^2)$，在字符串较长时非常低效。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        max_length = 0
        
        # 遍历每个可能的起始位置
        for i in range(n):
            # 使用集合来跟踪已经出现的字符
            char_set = set()
            current_length = 0
            
            # 从起始位置向后扩展
            for j in range(i, n):
                # 如果当前字符已经在集合中，表示遇到了重复字符
                if s[j] in char_set:
                    break
                
                # 将当前字符添加到集合中，并增加当前子串长度
                char_set.add(s[j])
                current_length += 1
            
            # 更新最大长度
            max_length = max(max_length, current_length)
        
        return max_length

方法二：滑动窗口 (Sliding Window)

破局点： 将子串理解成一个“小窗口”在移动，一直框选着符合条件的内容。

我们可以使用左右两个指针（left 和 i）来维护这个窗口。当右指针向右扩展遇到重复字符时，我们不需要让右指针回退，只需要让左指针向右收缩，直到把那个重复的字符“踢出”窗口即可。

算法步骤

  1. 初始化：左指针 left = 0，使用一个 Set (lookup) 来记录窗口内当前的字符集合。
  2. 移动右指针：将第一个元素添加进窗口，遍历字符串的每个字符被视为右指针的移动。
  3. 收缩窗口：如果发现右指针将要加入的字符已经存在于 lookup 中，则通过 while 循环不断将左指针 left 右移，并将移出窗口的最左侧字符从 lookup 中删除，直到满足条件。
  4. 更新结果：每次成功加入新字符后，记录目前的长度并和最大长度比较。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
            
        left = 0
        lookup = set()
        max_len = 0
        
        for i in range(len(s)):
            # 如果出现重复字符，移动左指针收缩窗口，直到重复字符被移除
            while s[i] in lookup:
                lookup.remove(s[left])
                left += 1
                
            # 将当前字符加入窗口
            lookup.add(s[i])
            # 更新最大长度记录
            max_len = max(max_len, i - left + 1)
            
        return max_len

精妙之处：安全剪枝
这就是滑动窗口解决这类问题的高效所在，它避免了暴力解法中的重复计算。外部的 for 循环明确执行 $n$ 次，关键在于内部的 while 循环：虽然它看起来可能在最坏情况下对每个字符都执行多次，但实际上，左指针 left 和扫描的索引 i 都只会单向向前移动。字符串中的每个字符最多只会被处理两次（一次进入窗口，一次由于左指针收缩被移出窗口），将时间复杂度从 $O(n^2)$ 优雅地降到了 $O(n)$。

复杂度分析

  • 时间复杂度分析：$O(n)$，其中 $n$ 是字符串的长度。左指针最多移动 $n$ 次，右指针遍历 $n$ 次，总执行次数受限于字符串长度。
  • 空间复杂度分析：$O(\min(m, n))$，其中 $m$ 是字符集的大小。因为在最坏情况下，lookup 集合最多包含字符集大小的字符数。

C++ 实现与 STL 容器扩充

在 C++ 中，类似的逻辑可以通过引入 <unordered_set> 容器来实现（使用哈希表保证 $O(1)$ 的查找）。对于这道题使用这种容器几乎是唯一解法，不使用 STL 会使其极度复杂（你需要自己实现类似哈希表的数据结构）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <string>
#include <unordered_set>
#include <algorithm>

using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.size() == 0) return 0;
        
        unordered_set<char> lookup;
        int maxStr = 0;
        int left = 0;
        
        for (int i = 0; i < s.size(); i++) {
            while (lookup.find(s[i]) != lookup.end()) {
                lookup.erase(s[left]);
                left++;
            }
            maxStr = max(maxStr, i - left + 1);
            lookup.insert(s[i]);
        }
        return maxStr;
    }
};

注：insert 方法用于向集合中添加元素，erase 方法用于删除指定元素，而 find 结合 end 返回值则用于检查元素是否存在。

ACM 模式

本节提供 ACM 竞赛风格的完整可运行代码，包含输入输出处理。

输入格式：

1
s

输入一行字符串。

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import sys

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
    n = len(s)
            max_length = 0

            # 遍历每个可能的起始位置
            for i in range(n):
                # 使用集合来跟踪已经出现的字符
                char_set = set()
                current_length = 0

                # 从起始位置向后扩展
                for j in range(i, n):
                    # 如果当前字符已经在集合中，表示遇到了重复字符
                    if s[j] in char_set:
                        break

                    # 将当前字符添加到集合中，并增加当前子串长度
                    char_set.add(s[j])
                    current_length += 1

                # 更新最大长度
                max_length = max(max_length, current_length)

            return max_length

def main():
    s = sys.stdin.read().strip()

    sol = Solution()
    result = sol.lengthOfLongestSubstring(s)
    print(result)

if __name__ == "__main__":
    main()

运行示例：

1
echo "abcabcbb" | python solution.py