[LEETCODE] Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

第一版

先做了一版slide window, length = ans, 每次都往前檢查 window內是不是有重複的字元

有的話就退出,沒有的話就把新的字元吃進來=>長度加一

大概只有50%的ranking…


第二版

這版優化了點 ,alphabets不用一直初始化,會記錄last s[j]最近的index,但還是只有優化一點點

而且code很不好理解,隔幾天再看我都快看不懂XD


第三版,Optimal Solution

這應該是最佳解,關鍵是利用重複字元先前的位置,節省掉檢查slide window內重複字元的動作

 

i,j可以看成不重覆字元的字串的頭尾

如果發現重複字元的話,把頭的pointer i移該字元第一次出現的index之後

因為如果後面還有更長字串的話,必定不能包含這兩個字串,所以得拋棄

 

舉個例子好了

“aewpkwfgxyz….”

再j往下走遇到第二個字元w之前,i一直不變,遇到之後第二個w之後,i指向p這個位置

但ans沒有變,因為目前aewpk 比 pkw更長,所以ans先維持住

到後面j走到x這個位置時,新的字串pkwfgx已經比原先的 aewpk長了,就更新ans~~~