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 intm := make(map[rune]bool)var left intfor _, c := range s {for m[c] {delete(m, rune(s[left]))left++}m[c] = trueif len(m) > longest {longest = len(m)}}return longest
}

---

參考文獻

3. 無重復字符的最長子串