Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
題目要求:
給定一個字串,在其中找一個最長的字母不重複的子字串。
By the way, substring指的是字母必須連在一起的子字串; 如果是 Subsequence就有點不大一樣,字母不一定要連在一起,只要是個順序即可。
思路:
Create一個 128大小的 integer array,index是 ASCII number代表每個 character,一個蘿蔔一個坑。Value代表那個字元上次出現的位置,初始值為 -1,代表尚未出現過。
另外,create 兩個 int position variable,分別紀錄目前正在運算中的增長中的子字串的起始位置,與目前位置。還需要一個 value variable來紀錄最大值。
例如:
給定字串:"abcabcdbc"
Index: 0 1 2 3 4 5 6 7 8
Char: a b c a d b f g c
Step1:
int lastCharPos[128],分別用來紀錄每個 character上次出現的位置,
初始化為 -1。
Step2:
'a', 'b', 'c'的ASCII code分別為:97, 98, 99,
所以lastCharPos array的值會變成:
Index: 0 1 2 ...... 97 98 99 ...... 127
int: -1 -1 -1 0 1 2 -1
代表 a, b, c上次分別出現在 position 0, 1 and 2。
Okay,現在 current position指向 pos 3的 a,查表發現 index 97 不是 -1,
這代表前面已經出現過 'a',這時就必須先做小計,計算這個子字串的長度,
因為這邊的子字串到此已經不能再延伸,必須捨棄掉上一個重複字元,
才能另外計算。
也就是說 current position 3 - start position 0 = 3 是發展到這邊,
暫時的最長字串。
然後我們必須捨棄上一個 'a',也就是把 start postion + 1,變成 1 ,
讓下一次的最長子字串計算不把他算進去,即可達到我們要的效果。
另外要注意的是,我們小計的 trigger時機點,只有發現字元的出現位置 >=
子字串的起始位置 ,才必須作小計,否則可以繼續延伸。例如我目前正在運
算的 substring的 start postion 是 8, 然後我查表發現我現在這個字元
上次出現的位置是 3,這個可以繼續延伸子字串。
因為這代表這個字元第一次出現在我正在運算的子字串裡,
上次出現已經是清朝的事了,現在都中華民國 104年了,ignore it.
Step3:
當current position跑到字尾時,要作最後一次的 substring length check,
這樣就萬無一失了。
實作: