這題的題目在這裡
題目會給定一個字串,要求我們計算,最長的不重複區間有多長?
不重複區間的定義,就是區間內的每個字元都不相同。
測試範例:
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: