###### 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:

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.