首頁LeetCode 筆記

# 題目

輸入一個字串 s，要找出最長的不含重複字元的子字串長度。

例子：

  • s = "abcabcbb" → 答案是 3 ("abc")
  • s = "bbbbb" → 答案是 1 ("b")
  • s = "pwwkew" → 答案是 3 ("wke")

# Sliding Window

window-1

上圖是大概的 Sliding Window 概念，用 set() 去重，並且用兩個指標 l 和 r 來表示目前的子字串範圍，然後不斷地擴展 r 直到遇到重複字元，就移動 l 指標來縮小子字串範圍，將重複字元去除

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

        for r in range(len(s)):
            while s[r] in charSet:
                charSet.remove(s[l])
                l += 1 # 縮減左邊界
            charSet.add(s[r]) # 新增右邊界
            # res = max(res, r - l + 1)
            res = max(res, len(charSet))
        return res

charSet 表示「從 i 到 j 之間，沒有重複字元的子字串」，其實也就是 = r - l + 1，相同意思，只是我用 len(charSet) 我自己認為更直觀點

  • Time Complexity: O(n)
  • Space Complexity: O(m)

# Brute Force

如果 s[j] 的字串已出現過在 charSet 裡面，就跳出 for j in range 迴圈，回到 for i in range 迴圈，重新創建 charSet

並記錄目前 charSet 的最大長度，每輪更新 max_unique_str_length

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_unique_str_length = 0
        for i in range(len(s)):
            charset = set() # charSet 永遠表示「從 i 到 j 之間，沒有重複字元的子字串」
            for j in range(i,len(s)):
                if s[j] in charset:
                    break
                charset.add(s[j])
            max_unique_str_length = max(max_unique_str_length ,len(charset))
        return max_unique_str_length
  • Time Complexity: O(n * m)
  • Space Complexity: O(m)