无重复字符的最长子串（LeetCode 3）

1.问题描述

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

s 由英文字母、数字、符号和空格组成。

示例 1：

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

示例 2：

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

示例 3：

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

2.难度等级

Medium。

3.热门指数

★★★★★

出题公司：阿里、腾讯、字节。

4.解题思路

方法一：暴力法

我们可以遍历字符串的所有字符，计算每个字符为起点的不含有重复字符的字串长度，记录到全局变量。

以示例 1 中的字符串 “abcabcbb” 为例，演示暴力法的求解过程。

以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)

所以最长子串长度为 3。

如何判断重复字符？

常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set 和 Golang 中的 map 等）。

时间复杂度： $O(n^2)$，n 为字符串长度。

空间复杂度： 最好为 O(1)，最坏为 O(n)。

方法二：滑动窗口

暴力法的求解过程，实际上存在不必要的检查。

以示例 1 中的字符串 “abcabcbb” 为例，演示暴力法的求解过程可优化的地方。

以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb

下面这一步是没有必要的，因为以 b 开始的不重复子串 bc 在上一个不重复子串内，长度肯定小于上一个不重复子串。
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb

以 abcab(c)bb 开始的最长字符串为 abcab(cb)b

同理，下面这一步也是没有必要的。
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b

以 abcabcb(b) 开始的最长字符串为 abcabcb(b)

在获取一个子串时，如果遇到了重复字符，那么获取下一个无重复字符的子串时，应该从重复字符的下一个字符开始。

将无重复字符的子串想象成一个滑动窗口，整个求解过程是移动滑动窗口的过程。

如何移动滑动窗口？

当出现重复字符时，我们只要把窗口内重复字符及其左边的元素移出就行了。

一直维持这样的窗口，直至窗口滑动到最后一个字符。记录最长的窗口长度，求出解！

时间复杂度： O(n)，n 为字符串长度。

空间复杂度： 最好为 O(1)，最坏为 O(n)。

下面以 Golang 为例，给出实现。

func lengthOfLongestSubstring(s string) int {
	var longest int
	m := make(map[rune]bool)
    var left int
	for _, c := range s {
		for m[c] {
			delete(m, rune(s[left]))
            left++
		}
        m[c] = true
        if len(m) > longest {
		    longest = len(m)
	    }
    }
	return longest
}

参考文献

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