---
# System prepended metadata

title: 3. Longest Substring Without Repeating Characters
tags: [sliding window, Leetcode, medium, python, Top 100 Liked Questions]

---

###### tags: `Leetcode` `medium` `sliding window` `python` `Top 100 Liked Questions`

# 3. Longest Substring Without Repeating Characters

## [題目來源:]https://leetcode.com/problems/longest-substring-without-repeating-characters/

## 題目:
Given a string s, find the length of the **longest substring** without repeating characters.

 
**Example 1:**
```
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
```
**Example 2:**
```
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
```
**Example 3:**
```
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
```

## 解題想法:
* 經典sliding window **SOP**:
    * 設兩pointer:
        * head、tail
    * 紀錄當前s[tail]
    * 當區間不合理:進while處理
        * head右移
    * tail右移

## python:
``` python=
from collections import defaultdict
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        #slide window
        head=0
        tail=0
        #紀錄出現字符次數
        dic=defaultdict(int)
        res=0
        while tail<len(s):
            dic[s[tail]]+=1
            while dic[s[tail]]>1:
                dic[s[head]]-=1
                if dic[s[head]]==0:
                    #清除空的
                    del dic[s[head]]
                head+=1
            res=max(res,tail-head+1)
            tail+=1
        return res
        
if __name__ == '__main__':
    result = Solution()
    s = "pwwkew"
    ans = result.lengthOfLongestSubstring(s)
    print(ans)

#Input: s = "pwwkew"
#Output: 3
#Explanation: The answer is "wke", with the length of 3.
#Notice that the answer must be a substring, 
#"pwke" is a subsequence and not a substring.
```
