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

题目描述

这是 LeetCode 上的 3. 无重复字符的最长子串 ，难度为 中等。

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

示例 1:

1
2
3
4
5
输入: s = "abcabcbb"

输出: 3 

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:
1
2
3
4
5
输入: s = "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:
1
2
3
4
5
6
输入: s = "pwwkew"

输出: 3

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

示例 4:
1
2
3
输入: s = ""

输出: 0

提示：

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

滑动窗口

定义两个指针 start 和 end， [start:end] 表示当前处理到的子串。

子串 [start:end] 始终满足要求：无重复字符。

从前往后进行扫描 s，用哈希表记录 [start:end] 中每字符的出现次数。

遍历过程中，end 不断自增，将第 end 个字符在哈希表中出现的次数加一。

令 right 为下标 end 对应的字符，当满足 map.get(right) > 1 时，代表此前出现过第 end 位对应的字符。

此时更新 start 的位置（使其右移），直到不满足 map.get(right) > 1 （代表 [start:end] 恢复满足无重复字符的条件），再用 [start:end] 长度更新答案。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        for (int start = 0, end = 0; end < s.length(); end++) {
            char right = s.charAt(end);
            map.put(right, map.getOrDefault(right, 0) + 1);
            while (map.get(right) > 1) {
                char left = s.charAt(start);
                map.put(left, map.get(left) - 1);
                start++;
            }
            ans = Math.max(ans, end - start + 1);
        }
        return ans;
    }
}

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        map = {}
        ans = 0
        start = 0
        for end in range(len(s)):
            right = s[end]
            map[right] = map.get(right, 0) + 1
            while map[right] > 1:
                left = s[start]
                map[left] = map[left] - 1
                start += 1
            ans = max(ans, end - start + 1)
        return ans

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> map;
        int ans = 0;
        for (int start = 0, end = 0; end < s.length(); end++) {
            char right = s[end];
            map[right] = map[right] + 1;
            while (map[right] > 1) {
                char left = s[start];
                map[left] = map[left] - 1;
                start++;
            }
            ans = max(ans, end - start + 1);
        }
        return ans;
    }
};

TypeScript 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function lengthOfLongestSubstring(s: string): number {
  const map: { [key: string]: number } = {};
  let ans = 0;
  let start = 0;
  for (let end = 0; end < s.length; end++) {
      const right = s.charAt(end);
      map[right] = (map[right] || 0) + 1;
      while (map[right] > 1) {
          const left = s.charAt(start);
          map[left] = (map[left] || 0) - 1;
          start++;
      }
      ans = Math.max(ans, end - start + 1);
  }
  return ans;
};

  • 时间复杂度：虽然有两层循环，但每个字符在哈希表中最多只会被插入和删除一次，复杂度为 $O(n)$
  • 空间复杂度：使用了哈希表进行字符记录，复杂度为 $O(n)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.3 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。