解題教學 : Leetcode #3 Longest Substring Without Repeating Characters

這題的題目在這裡

Longest Substring Without Repeating Characters - LeetCode

題目會給定一個字串，要求我們計算，最常的不重複區間有多長?

不重複區間的定義，就是區間內的每個字元都不相同。

測試範例:

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.

約束條件:

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

演算法:

這題比較困難的點在於要想到滑窗(Sliding window)結合字典(Hash table)的演算法。

設計一個滑窗，從左到右掃描。

檢查當下這個字元以前是否出現過，

如果出現過，就收縮左邊界到最後一次出現的位置+1

如果沒有出現過，就繼續擴展右邊界，並且更新當下這個字元最後一次出現的位置。

接著，計算窗口大小，

並且update最大的 不重複區間大小 = 不重複窗口大小。

程式碼:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        
        # record of longest substring wihtout repetition
        window_length = 0
        
        # left index of sliding window [start, end] inclusively
        start = 0
        
        # key: character
        # value: latest index of character on left hand side
        latest_index = defaultdict( lambda : -1)
        
        # slide right index of sliding window, from 0
        for end in range(len(s)):
            
            cur_char = s[end]

            # If current character has showed up before, and last position is inside sliding window
            # then shrink to right-hand side to avoid repetition
            if latest_index[cur_char] >= start:
                
                start = latest_index[cur_char] + 1
                
            
            # update last occurrence index of current character
            latest_index[ cur_char ] = end
            
            # update longest length of sliding window
            window_length = max( window_length, end - start + 1)

        return window_length

時間複雜度:

O(n) 滑窗從左到右掃描過一遍

空間複雜度:

空間成本落在字典(Hash table)上。

O(1) = O( character set ) 只有小寫英文字母，數字，符號，和空白。

Reference:

[1] Python/JS/Java/C++ O(n) by sliding window [w/ Visualization] — Longest Substring Without Repeating Characters — LeetCode