題目來源：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

1 題目描述

這道題目要求我們在給定的字符串 s 中找到不含重複字符的最長子字符串的長度。

2 解法

2.1 暴力解

簡單粗暴些，找一個最長子字串，那麼我們用兩個迴圈窮舉所有子串，然後再用一個函數判斷該子字串中有沒有重複的字元。

def isUnique(s: str, start: int, end: int):
    """end 不包含"""
    substring = {}
    for i in range(start, end):
        if substring.get(s[i]):
            return False
        else:
            substring[s[i]] = 1
    return True


class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        ans = 0
        max_left = 0
        max_right = 0
        for left in range(len(s)):
            for right in range(len(s)):
                if isUnique(s, left, right) and ans < (right-left):
                    ans = right - left
                    max_left = left
                    max_right = right
        return ans, s[max_left:max_right]

isUnique

時間複雜度：O(m) 其中 m 是被檢查子字符串的長度，這是因為 isUnique 函數在檢查從 start 到 end 的每個字符是否唯一。
空間複雜度：O(m)，其中 m 是被檢查子字符串的長度。這是因為函數使用了一個字典 substring 來存儲子字符串中的字符。

lengthOfLongestSubstring 方法

時間複雜度：O(n^3)，其中 n 是字符串 s 的長度。
- 外層的 for 循環有 n 次迭代。
- 內層的 for 循環有 n 次迭代。
- 每次調用 isUnique 函數，其時間複雜度為 O(m)，m 最長可能為 n。
- 所以總的時間複雜度為 O(n) * O(n) * O(n) = O(n^3)。
空間複雜度：O(min(m,n))。m 這是由於在調用 isUnique 函數時使用的字典 substring 所需的空間， n 是字符集的大小。

2.2 滑動窗口

我們可以透過 sliding window 檢查子字串是否有重複的字元

如果有，我們就將左指針向右移動一格，直到子字串中沒有重複的字元為止。
如果沒有，左指針不動，右指針向右移動一格。

如下所示：

檢查的時候主要移動 right: 如果沒有重複的字元，就將 right 指針向右移動，並且將對應的字元存儲到 substring 中。
- ‘abc’ -> ‘abcd’ -> ‘abcda’ (發現重複的字元)
一但發現重複的字元，就將 left 指針向右移動，直到子字串(hashTable)中沒有重複的字元為止。
- ‘abcda’ -> ‘bcda’(left向右+1，'a’不見了)
重複上述步驟，直到 right 指針遍歷完整個字符串。

但是需要注意的是，如果 left 指針向右移動，我們需要將 substring 中的對應字元刪除。

class Solution(object):
    def lengthOfLongestSubstring2(self, s):
        """
        :type s: str
        :rtype: int
        """
        n = len(s)
        substring = {}
        ans, left, right = 0,0,0
        max_left, max_right = 0,0
        while (left < n and right < n):
            if not substring.get(s[right]):
                substring[s[right]] = right # 存儲字元和對應的索引
                right = right + 1
                if ans < right-left:
                    ans = right-left
                    max_left = left
                    max_right = right
            else:
                substring.__delitem__(s[left]) # 刪除重複的字元
                left = left + 1 # 左指針向右移動
        return ans, s[max_left:max_right] #(4, 'abcd')

時間複雜度：O(2n) = O(n)
在這段代碼中，最外層的 while 迴圈會迭代 right 指針從 0 到 n，並且每當遇到重複字符時，left 指針也會向右移動。因此，無論哪種情況，每個字符最多只會被處理兩次（一次由 right，一次由 left），因此總的時間複雜度為 O(2n)，基本上就是 O(n)。

right 指針在整個字符串上移動，每次移動都進行一次查找和插入操作，這些操作的時間複雜度是常數時間 O(1)。
當遇到重複字符時，left 指針移動並刪除字典中的對應項目，這也是常數時間 O(1)。

空間複雜度 O(min(m,n))

和上面類似，需要一個Hash保存子串，所以是O(min(m,n))，m 是字符集的大小。n 是字符串 s 的長度。

2.3 改良滑動窗口

繼續優化，我們看上邊的演算法的一種情況。當 right 往前 +1 一格時，此時 left 向前移到 b ,此時子字串中仍然含有 c，還得繼續移動，所以這裡其實可以優化。我們可以一步到位，直接移動到子字串 c 的位置的下一位！

def lengthOfLongestSubstring3(self, s):
    """
    :type s: str
    :rtype: int
    """
    n = len(s)
    maxLength, max_left, max_right = 0, 0, 0 
    charMap = {}
    left = 0

    for right in range(n):
        # 如果是全新的單字，並且 right 沒有超過 left
        if s[right] not in charMap or charMap[s[right]] < left:
            # 把新的字元加入 charMap value 是 index
            charMap[s[right]] = right
            # 檢查新字元的加入是否有超過目前的最長子字串
            if maxLength < right - left + 1:
                maxLength = right - left + 1
                max_left = left
                max_right = right + 1
        else:
            # 關鍵在這裡，直接移動到子字串 c 的位置的下一位
            left = charMap[s[right]] + 1
            # 並且更新 charMap 的 index 位置
            charMap[s[right]] = right

    return maxLength, s[max_left:max_right]

3 總結

這個題目的重點在於：

hash table 主要是用來存儲子字串中的字元，並且可以快速查找是否有重複的字元。
- 使時間與空間複雜度都是 O(m)，m 表示欲檢查的子字串長度。
sliding window 負責處理連續子字串的問題，並且可以快速移動左右指針。
- sliding window 的右向檢查方式，使得每個字元最多只會被處理兩次，因此時間複雜度是 O(2n) 也就是 O(n)。