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

閱讀時間約 4 分鐘
raw-image

這題的題目在這裡

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

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


測試範例:

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.


raw-image

這題比較困難的點在於要想到滑窗(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

85會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目的輸入會給我們一個串列,要求我們從頭到尾反轉整個串列。 例子: 如果輸入是1 -> 2 -> 3,那麼輸出就是 3 -> 2 -> 1
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
題目會給定我們一個陣列,還有一個整數值x 問我們每次從陣列頭部或尾部取一個整數,最少需要幾次才能使取出的整數總和為x?
題目的輸入會給我們一個串列,要求我們從頭到尾反轉整個串列。 例子: 如果輸入是1 -> 2 -> 3,那麼輸出就是 3 -> 2 -> 1
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
題目會給定我們一個陣列,還有一個整數值x 問我們每次從陣列頭部或尾部取一個整數,最少需要幾次才能使取出的整數總和為x?
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
Thumbnail
最難考題「創意的頭部型態」,收盤 13:30 收件 為破解長期「Allmoneyrise」投資群組散佈不實投資觀念與股價訊息,本題目獎金加碼,鼓勵蛙友踴躍作答 第一名一位,獎金7-11禮券500元,第二名三位,獎金7-11禮券300元,佳作七名,獎金7-11禮券200元 這題陷阱處處,提醒小心
Thumbnail
亞斯先生對外是客氣有禮的紳士,對家人則是自我中心的固執老爹常跟一般人有不同觀點,即使夫妻多年你仍搞不懂他到底在想什麼(因為他自己也沒意識啦)常常雙標說一套做一套(這是因為理智與情感不連線,他理智時多追求CP值,情緒中時則比小孩還盧,標準不同且本人無自覺),讓人不知道怎麼跟他相處
Thumbnail
題目會給定一個字串,要求我們計算,最長的不重複區間有多長? 不重複區間的定義,就是區間內的每個字元都不相同。
Thumbnail
中二病少女這次去了外星球,化身複製人大軍,身穿帝國的暴風兵裝備,這次一樣用realistic fantasy模型,再搭配其他的(你知道的專作瑟瑟圖的那種模型)試試看效果,去呈現荒涼外星球的戰鬥。但星際大戰的光劍始終都很怪很可笑,等下可以看。 這次表情沒下提示詞連笑都不笑,同伴倒下也呈現呆滯狀,表現的
Thumbnail
本篇大眾占卜由𝓝𝓸𝓿微微去冰/水晶投稿 ●選項A 你最離不開的是戀人 你本身是一個追求浪漫和溫馨的人,你非常的重視愛情,所以,最離不開的是戀人。目前單身的你,應該很嚮往一份美好真摯的愛情,知你冷暖,甚至想好好地被呵護關懷。而戀愛中的你,應該有一個不錯的伴侶,他溫柔又體貼,時刻都將你入心,
Thumbnail
〈赤壁賦〉是高中國文的經典課文,其中第五段蘇子闡述「變與不變」的道理堪稱核心古文15篇裡面最難解釋的一個段落,實習的時候有老師這麼跟我說: 「教甄試教抽到〈赤壁賦〉就可以準備回家了。」 「因為100個老師的心目中有100個〈赤壁賦〉。」
Thumbnail
這本書是108年讀完的,最近又看到電影"找到你"的解說,讓我想到它,過往日子,一直強調務必反省與修正,但多的人是步驟與實體修正,更需要看法改變才行。 這本書較注重自我觀念改善,人生可能都再重複相同錯誤;比如說平常男友很樂意載你,但有次他以為不需載而未詢問,導致妳以為他不喜歡妳,一次的想法不同就失去信
Thumbnail
寫於05/02/2020 一下巴士,對Byron Bay的第一印象是很慢步調、慵懶,讓我聯想到都蘭。很多裸上身、赤腳、古銅色肌膚的男孩手上拿著衝浪板,不是在前往就是從海邊回來的路上。 到達的時候是早上八九點,先寄放好行李接著在街上遊蕩等待check in。很多漂亮精緻的早午餐店但是都很貴,最後去了
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
題目敘述 Longest Arithmetic Subsequence of Given Difference 給定一個整數陣列nums,請找出給定公差difference的最長的等差數列的長度是多少?
Thumbnail
題目敘述 Longest Palindromic Subsequence 給定一個字串s,請找出字串s的最長回文子序列的長度。 註: 子序列 不要求一定要連續。 測試範例 Input: s = "bbbab" Output: 4
Thumbnail
最難考題「創意的頭部型態」,收盤 13:30 收件 為破解長期「Allmoneyrise」投資群組散佈不實投資觀念與股價訊息,本題目獎金加碼,鼓勵蛙友踴躍作答 第一名一位,獎金7-11禮券500元,第二名三位,獎金7-11禮券300元,佳作七名,獎金7-11禮券200元 這題陷阱處處,提醒小心
Thumbnail
亞斯先生對外是客氣有禮的紳士,對家人則是自我中心的固執老爹常跟一般人有不同觀點,即使夫妻多年你仍搞不懂他到底在想什麼(因為他自己也沒意識啦)常常雙標說一套做一套(這是因為理智與情感不連線,他理智時多追求CP值,情緒中時則比小孩還盧,標準不同且本人無自覺),讓人不知道怎麼跟他相處
Thumbnail
題目會給定一個字串,要求我們計算,最長的不重複區間有多長? 不重複區間的定義,就是區間內的每個字元都不相同。
Thumbnail
中二病少女這次去了外星球,化身複製人大軍,身穿帝國的暴風兵裝備,這次一樣用realistic fantasy模型,再搭配其他的(你知道的專作瑟瑟圖的那種模型)試試看效果,去呈現荒涼外星球的戰鬥。但星際大戰的光劍始終都很怪很可笑,等下可以看。 這次表情沒下提示詞連笑都不笑,同伴倒下也呈現呆滯狀,表現的
Thumbnail
本篇大眾占卜由𝓝𝓸𝓿微微去冰/水晶投稿 ●選項A 你最離不開的是戀人 你本身是一個追求浪漫和溫馨的人,你非常的重視愛情,所以,最離不開的是戀人。目前單身的你,應該很嚮往一份美好真摯的愛情,知你冷暖,甚至想好好地被呵護關懷。而戀愛中的你,應該有一個不錯的伴侶,他溫柔又體貼,時刻都將你入心,
Thumbnail
〈赤壁賦〉是高中國文的經典課文,其中第五段蘇子闡述「變與不變」的道理堪稱核心古文15篇裡面最難解釋的一個段落,實習的時候有老師這麼跟我說: 「教甄試教抽到〈赤壁賦〉就可以準備回家了。」 「因為100個老師的心目中有100個〈赤壁賦〉。」
Thumbnail
這本書是108年讀完的,最近又看到電影"找到你"的解說,讓我想到它,過往日子,一直強調務必反省與修正,但多的人是步驟與實體修正,更需要看法改變才行。 這本書較注重自我觀念改善,人生可能都再重複相同錯誤;比如說平常男友很樂意載你,但有次他以為不需載而未詢問,導致妳以為他不喜歡妳,一次的想法不同就失去信
Thumbnail
寫於05/02/2020 一下巴士,對Byron Bay的第一印象是很慢步調、慵懶,讓我聯想到都蘭。很多裸上身、赤腳、古銅色肌膚的男孩手上拿著衝浪板,不是在前往就是從海邊回來的路上。 到達的時候是早上八九點,先寄放好行李接著在街上遊蕩等待check in。很多漂亮精緻的早午餐店但是都很貴,最後去了