# **Leetcode筆記(Longest Substring Without Repeating Characters)**

:::info
:information_source: 題目 : Longest Substring Without Repeating Characters, 類型 : string , 等級 : medium
日期 : 2023/03/04，2023/05/10，2023/06/27，2023/09/21，2023/12/03，2024/02/20，2025/02/25
:::

### 嘗試

時間複雜度O(n)，空間複雜度O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        wordSet = set()
        maxList = []
        maxnum = 0

        for i in range(len(s)):
            wordSet.add(s[i])
            if s[i] in wordSet:
                maxList.append(len(wordSet))
                wordSet.clear()
        return max(maxList)

2023/05/10

# set語法
set.remove()
set.add()

# 因為要substring 所以一定是連在一起的
# 毛毛蟲移動法
# 前頭碰到一樣的就收後尾


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        record = set()
        res = 0
        l = 0

        for r in range(len(s)):
            while s[r] in record:
                # 收後尾
                record.remove(s[l])
                l += 1
            # 探前頭
            record.add(s[r])
            res = max(res, r - l + 1)
        
        return res

2023/06/27
毛毛蟲移動法(用於substring)，前頭碰到一樣的就收後尾
有r, l ，如果r遇到重複的字母，l則會往回縮直到重覆字母不見

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        record = set()
        length = 0
        l = 0
        for r in range(len(s)):
            while s[r] in record:
                record.remove(s[l])
                l += 1
            record.add(s[r])
            length = max(length, (r - l) + 1)
        
        return length

2023/09/21
改用r去往前延伸

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        record = set()
        l, r = 0, 0
        maxLen = 0

        while r < len(s):
            while r < len(s) and not s[r] in record:
                record.add(s[r])
                r += 1

            maxLen = max(maxLen, r - l)
            record.remove(s[l])
            l += 1
        
        return maxLen

2023/12/03

"""
s = "abcabcbb"

l, r = 0, 0
maxRes = 
set
while r < len(s):
    while s[r] in set:
        pop out s[l]
    set.add(s[r])
    update the maxRes
"""

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        maxRes = 0
        record = set()
        l, r = 0, 0
        while r < len(s):
            while s[r] in record:
                record.remove(s[l])
                l += 1
            record.add(s[r])
            r += 1
            if len(record) > maxRes:
                maxRes = len(record)
        
        return maxRes

2024/02/20

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l, r = 0, 0
        visited = set()
        maxL = 0

        while r < len(s):
            while s[r] in visited:
                visited.remove(s[l])
                l += 1
                
            print(visited)
            visited.add(s[r])
            maxL = max(maxL, r - l + 1)
            r += 1
        
        return maxL

2025/02/25

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        res = 0
        l, r = 0, 0
        record = set()

        while r < len(s):
            while s[r] in record:
                record.remove(s[l])
                l += 1
            record.add(s[r])
            res = max(res, r - l + 1)
            r += 1
            
        return res

---
### **優化**

時間複雜度O(n)，空間複雜度O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        wordSet = set()
        l = 0
        maxLen = 0

        for i in range(len(s)):
            while s[i] in wordSet: # 反覆執行直到重複的都被拿掉
                wordSet.remove(s[l])
                l += 1
            wordSet.add(s[i])
            maxLen = max(maxLen, len(wordSet))

        return maxLen

---

**:warning: 錯誤語法**
:::warning
while代表重複執行
:::

**:thumbsup:學習**
:::success
sliding_window:用一個指標去追蹤與更新
若這個set的第n個字被移走後，要記得n+1
:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=wiGpQwVHdE0
Provided by. NeetCode

###### tags: `string` `medium` `leetcode`