无重复字符的最长子串

题目描述

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

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

提示：

  • 0 <= s.length <= 5 * 10^4
  • s 由英文字母、数字、符号和空格组成

解题思路

这道题的最优解法是使用 滑动窗口 算法，通过维护一个滑动窗口 window （通常为 Map 类型）来记录当前不包含重复字符的子串，并且较为简单，不需要保存 need 。

核心思路

  1. 使用两个指针 left 和 right 分别表示滑动窗口的左右边界
  2. 使用哈希表（HashMap）记录窗口内的字符及其出现次数
  3. 右指针 right 不断向右移动，将当前字符加入窗口
  4. 如果当前字符在窗口中已经存在（出现次数大于1），则左指针 left 向右移动，直到窗口中不再包含重复字符
  5. 每次移动右指针时，更新最长子串的长度

算法步骤

  1. 初始化 left = 0，right = 0，maxLength = 0
  2. 创建一个哈希表 window 来存储字符及其出现次数
  3. 右指针 right 遍历字符串：
    • 将当前字符 s[right] 加入窗口，更新其出现次数
    • 如果当前字符出现次数大于1，则左指针 left 向右移动，同时减少对应字符的出现次数，直到当前字符出现次数等于1
    • 更新最长子串长度：maxLength = max(maxLength, right - left + 1)
  4. 返回 maxLength

代码实现

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        HashMap<Character, Integer> window = new HashMap<>();
        int maxLength = 0;
        int left = 0, right = 0;
        for ( ; right < s.length(); right++) {
            char curChar = s.charAt(right);
            window.put(curChar, window.getOrDefault(curChar, 0) + 1);
            while (window.get(curChar) > 1 && left <= right) {
                char deleteChar = s.charAt(left);
                window.put(deleteChar, window.get(deleteChar) - 1);
                left++;
            }
            maxLength = Math.max(right - left + 1, maxLength);
        }
        return maxLength;
    }
}

C++ 实现

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 <unordered_map>
#include <string>
#include <algorithm>

class Solution {
public:
    int lengthOfLongestSubstring(std::string s) {
        if (s.size() == 1) {
            return 1;
        }
        int left = 0, right = 0;
        std::unordered_map<char, int> win;
        int res = 0;
        while (right < s.size()) {
            char ch = s[right];
            win[ch]++;
            while (win[ch] > 1) {
                win[s[left]]--;
                left++;
            }
            res = std::max(res, right - left + 1);
            right++;
        }
        return res;
    }
};

复杂度分析

  • 时间复杂度： O(n)，其中 n 是字符串的长度。左指针和右指针分别最多移动 n 次。
  • 空间复杂度： O(min(m, n))，其中 m 是字符集的大小。哈希表最多需要存储 m 个不同的字符。

总结

这道题是滑动窗口算法的经典应用。通过维护一个动态调整的窗口，我们可以在一次遍历中找到最长无重复字符子串，时间复杂度为 O(n)。

同时还可以看到，C++ 和 Java 语言在 Map 接口上使用的不同，Java 更喜欢用 Map.xxx(key, val) 方法来获取默认值，而 C++ 则更倾向于使用 Map[index] 运算符。

滑动窗口算法是解决字符串相关问题的常用技巧，特别是在处理子串、子数组等连续问题时非常有效。