最長的不重複區間 Leetcode #3 Longest Substring w/o Repeating Chars

這題的題目在這裡

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

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

測試範例:

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 subst

約束條件:

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