Longest Substring Without Repeating Characters - LeetCode

May 19, 2024

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        longest = 0
        start = 0
        visited = set()
        
        for end in range(len(s)):
            # check if the window is valid (unique), if not, shrink it untile it is valid
            while s[end] in visited:
                tail = s[start]
                visited.remove(tail)
                start += 1
            
            visited.add(s[end])
            longest = max(end - start + 1, longest)
        
        return longest

time: O(n)

space: O(1) because s has only specific letters

概念：

使用一個sliding window (two pointer)來檢查當前的substring是某有重複

每次回圈移動一格右邊指針，把遇到的字母與他出現的index記錄在hash map裏面，{a:0}

如果遇到的字母在hash map裡面出現過的話，就要縮小window：看現在的左邊指與成hash map裡面那個index +1哪個大，變成那個

每次回圈結束前，如果現在window長度比之前的window長，就更新一個window長度

最後回傳window長度

演算法：

宣告兩個pointer: r, l，一開始都是0(指向第一個位置)

宣告一個map，用來存字母上次出現時的index