頭條2019校招筆試題 第一題 最長無重複子串：leetcode3-Longest Substring Without Repeating Characters

leetcode3-Longest Substring Without Repeating Characters

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.

頭條題：

給定一個字元串，輸出 最長無重複子串的長度。

輸入：

abcabcbb
           

輸出：

3
           

第一個思路：

建立一個字典zs_dic來裝最長無重複子串裡的字元，裡面格式是 字元：字元在原始字元串的位置。字典的好處在于索引的複雜度是O(1)，位置是為了後面删元素的時候好索引。

start和end指針用來記錄子串的開頭（字典的起始字元）和結尾（字典的結束字元）。

當出現dic裡不存在的元素後，接着要删除字典裡 原始字元串從start位置 到 dic裡面該字元在原始字元串的位置 的所有字元。每删除一個，start+1，向後挪動，直到指向重複元素的後一個字元。

舉個例子：

‘abebf’

當start指向a，end一直累加到指向第二個b時結束添加dic的循環，dic裡的元素{a,b,e}，

因為b在dic裡出現了，要删掉字典裡包括b及b之前的字元，也就是b,a。這時，就能利用到字典裡每個鍵的值（位置）。删掉ba後dic變成{e}，start每删掉一個就要+1，這樣就剛好指到e，也就是dic起始元素的位置。

現在end還是指向b，就能重新将b加入到字典裡，f又加到字典裡。最後得到字典{e,b,f}。

子串更新後是nmax=3

注意，這個dic裡記錄的最長無重複子串，nmax即是子串的長度。

代碼：

def Maxlens(s):
    start=end=
    #dic key：字元 value:字元的索引
    zs_dic={}
    nmax=
    while(end<len(s)):
        while(end<len(s) and s[end] not in zs_dic):
            zs_dic[s[end]]=end
            end=end+
        #count記錄不重複子串的長度
        count=end-start
        nmax=max(count,nmax)
        if (end != len(s)):
            for i in range(zs_dic[s[end]],start-,-):
                del zs_dic[s[i]]
                start=start+
    return nmax
           

第二個思路2：

kdic用來記錄目前出現過的字元（不存在重複）。kdic[astr[i]] = i，鍵表示字元，值表示字元在原始字元串的位置。

begin記錄子串的起始位置。

對原始字元串從頭開始掃描每一個字元，如果字元在kdic出現過了，且字元串的初始值begin要重新指派到重複字元+1

舉個例子：

‘abebf’

kdic是{a:0,b:1,e:2}，i=3時指向b，b出現在kdic裡，且begin=0<=kdic[b]=1的位置，表示指針要重新指派。于是把kdic[b]+1的位置，也就是b後面一個字元f的位置指派給begin,現在begin就指向了f。最大長度就是(i-begin+1)

def Maxlens1(astr):
    begin = num = 
    kdic = {}
    for i in range(len(astr)):
        if(astr[i] in kdic and begin <= kdic[astr[i]]):
            begin = kdic[astr[i]] + 
        else:
            num = max(num, i - begin + )
        kdic[astr[i]] = i
    return num