无重复字符的最长子串

题目描述

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

数据样例

示例 1:

1
2
3

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

示例 2:

1
2
3

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

示例 3:

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

提示：

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

双指针，哈希表 - $O(N)$

双指针，哈希表

首先考虑直接暴力枚举，那么需要枚举所有的字串，枚举一个字符串的所有字串，由于字符串的字串是连续的，因此可以通过枚举字串的开始位置和结束位置来枚举所有的字串，如下图所示：

第一层循环枚举图中 $1$，第二层循环枚举图中 $2$
两个之间就是当前枚举的字串，图中的 cabc

由于需要两层循环枚举，因此时间复杂度是 $O(N ^ 2)$，需要进行优化

我们观察发现，枚举的过程中，有些时候是不需要枚举的：

不合法情况：
- 当出现不合法的情况的时候，假设当前字串中已经出现相同的字符了。如下图中的红色字串。
- 那么当 $1$ 往后面移动的时候，其实 $2$ 不需要从头开始枚举。如下图中的紫色的部分，$2$ 并不需要枚举这部分。因为上图中 cabc 就已经出现相同的字符了，后面指针 $1$ 移动后，指针 $2$ 如果是紫色部分的话，那么必然也都包含 cabc 这个串，因此也一定都是不合法的。
合法情况：
- 如果当前两个指针 $1, 2$ 之间的字串是合法的，那么此时 $2$ 指针不需要向前移动，因为一定都是合法的。因为为了寻找更长的合法的字串，那么此时我们应该将 $1$ 向前移动一个位置。

因此：我们枚举 $1$ 指针时候，每次 $2$ 指针不需要从开头进行枚举

算法步骤：

和暴力枚举一样，我们首先枚举指针 $1$，也就是说枚举字串的右端点。
指针 $2$ 从头开始枚举，此时我们分析两个指针构成的字串的情况
- 如果当前字串是不合法的，那么 $2$ 向前移动一个位置：这个和暴力枚举一样，继续向后寻找可能存在的合法的更小的字串。
- 如果当前字串是合法的，那么 $1$ 向前移动一个位置，同时指针 $2$ 的位置保持不变
  - 指针 $2$ 之前的所有位置一定都是不合法的（因为只有不合法才移动指针 $2$）。
  - 指针 $2$ 之后的所有位置一定都是合法的：之前我们讲解了对于合法情况，为了寻找更长的合法的字串，那么此时我们应该将 $1$ 向前移动一个位置。
判断字串是否合法：利用哈希表记录当前字串中各个字符的是否出现过即可。
- 当前枚举指针 $1$ 的时候，将新的字符加入到哈希表中
- 当枚举指针 $2$ 向前的时候，将当前的字符从哈希表中删除即可

时间复杂度 - $O(N)$

由于指针只会超一个方向移动，因此整体时间复杂度是 $O(N)$

代码

func lengthOfLongestSubstring(s string) int {
    n, st := len(s), map[byte]bool{}
    res := 0
    for i, j := 0, 0; i < n; i++ {
        for j <= i && st[s[i]] { st[s[j]] = false; j++ }
        res = max(res, i - j + 1)
        st[s[i]] = true
    }
    return res
}

func max(x, y int) int { if x < y { return y }; return x }

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> vis;
        int res = 0;
        int slen = s.size();
        for (int i = 0, j = 0; i < slen; ++i) {
            while (j <= i && vis[s[i]]) vis[s[j]] = 0, j++;
            res = max(res, i - j + 1);
            vis[s[i]] = 1;
        }
        return res;
    }
};