# 0003. 無重復字符的最長子串 ## 題目地址(3. 無重復字符的最長子串) <https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/> ## 題目描述 給定一個字符串，請你找出其中不含有重復字符的 最長子串 的長度。 示例 1: 輸入: "abcabcbb" 輸出: 3 解釋: 因為無重復字符的最長子串是 "abc"，所以其長度為 3。 示例 2: 輸入: "bbbbb" 輸出: 1 解釋: 因為無重復字符的最長子串是 "b"，所以其長度為 1。 示例 3: 輸入: "pwwkew" 輸出: 3 解釋: 因為無重復字符的最長子串是 "wke"，所以其長度為 3。 請注意，你的答案必須是 子串 的長度，"pwke" 是一個子序列，不是子串。 ``` <pre class="calibre18">``` ## 前置知識 - 哈希表 - [滑動窗口](https://github.com/azl397985856/leetcode/blob/master/thinkings/slide-window.md) ## 公司 - 阿里 - 字節 - 騰訊 ## 思路 用一個 hashmap 來建立字符和其出現位置之間的映射。同時維護一個滑動窗口，窗口內的都是沒有重復的字符，去盡可能的擴大窗口的大小，窗口不停的向右滑動。 （1）如果當前遍歷到的字符從未出現過，那么直接擴大右邊界； （2）如果當前遍歷到的字符出現過，則縮小窗口（左邊索引向右移動），然后繼續觀察當前遍歷到的字符； （3）重復（1）（2），直到左邊索引無法再移動； （4）維護一個結果 res，每次用出現過的窗口大小來更新結果 res，最后返回 res 獲取結果。  (圖片來自： https://github.com/MisterBooo/LeetCodeAnimation) ## 關鍵點 1. 用一個 mapper 記錄出現過并且沒有被刪除的字符 2. 用一個滑動窗口記錄當前 index 開始的最大的不重復的字符序列 3. 用 res 去記錄目前位置最大的長度，每次滑動窗口更新就去決定是否需要更新 res ## 代碼 代碼支持：Python3 Python3 Code: ```python from collections import defaultdict class Solution: def lengthOfLongestSubstring(self, s: str) -> int: l = 0 ans = 0 counter = defaultdict(lambda: 0) for r in range(len(s)): while counter.get(s[r], 0) != 0: counter[s[l]] = counter.get(s[l], 0) - 1 l += 1 counter[s[r]] += 1 ans = max(ans, r - l + 1) return ans ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(N)O(N)O(N) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。