力扣经典150题第三十一题：无重复字符的最长子串

无重复字符的最长子串问题详解与解决方法

1. 介绍

无重复字符的最长子串问题是 LeetCode 经典题目之一，要求找出一个给定字符串中不含有重复字符的最长子串的长度。

问题描述

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

示例

1. 输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
2. 输入: s = “bbbbb” 输出: 1 解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
3. 输入: s = “pwwkew” 输出: 3 解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

2. 解题思路

使用滑动窗口（双指针）和哈希集合的方法解决该问题：

• 使用两个指针 left 和 right 表示滑动窗口的左右边界，初始都指向字符串的开头。
• 使用哈希集合 set 存储当前窗口内的字符，初始为空。
• 遍历字符串 s，右指针 right 不断向右移动，将字符加入 set 中，直到遇到重复字符。
• 如果遇到重复字符，则左指针 left 向右移动，直到将重复字符移出窗口，同时从 set 中移除这些字符。
• 在遍历过程中，不断更新最长子串的长度。

3. 算法实现

public int lengthOfLongestSubstring(String s) {
    int n = s.length();
    Set<Character> set = new HashSet<>();
    int maxLength = 0, left = 0, right = 0;
    
    while (right < n) {
        char ch = s.charAt(right);
        while (set.contains(ch)) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(ch);
        maxLength = Math.max(maxLength, right - left + 1);
        right++;
    }
    
    return maxLength;
}

4. 复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。两个指针 left 和 right 各遍历一次字符串。
• 空间复杂度：O(min(m, n))，其中 m 是字符集的大小（假设为常数，比如英文字母），n 是字符串 s 的长度。哈希集合 set 最多存储字符集的大小个元素。

5. 测试与验证

设计不同测试用例，包括空字符串、全重复字符、无重复字符等情况，验证算法的正确性和效率。

6. 总结

无重复字符的最长子串问题是一个经典的滑动窗口应用问题。通过本文的详细讲解和算法实现，可以有效地解决该问题，找出字符串中不含重复字符的最长子串的长度。

7. 参考文献

• LeetCode 官方网站
• 《算法导论》
• 《程序员面试金典》

感谢阅读！