Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

Subscribe to see which companies asked this question

找出最長(zhǎng)序列的長(zhǎng)度赡译，一個(gè)可行的辦法是轉(zhuǎn)換成ascii碼，然后遍歷字符串庶香，

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = 0
        maxlen = 0
        hashtable = [-1 for i in range(256)]
        for i in range(len(s)):
            if hashtable[ord(s[i])] != -1:
                while start <= hashtable[ord(s[i])]:
                    hashtable[ord(s[start])] = -1
                    start += 1
            if i - start + 1 > maxlen:
                maxlen = i - start + 1
            hashtable[ord(s[i])] = i
        return maxlen

還有一個(gè)更巧妙的實(shí)現(xiàn)：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        ind = {}
        w = 0
        m = 0
        for i in range(0, len(s)):
            c = s[i]
            if i == 0:
                ind[c] = 1
                m = 1
            else:
                if c not in ind or ind[c] < w:
                    ind[c] = i+1
                    d = i+1 - w
                    m = d if d > m else m  
                else:
                    w = ind[c]
                    ind[c] = i+1            
        return m

下面的版本超級(jí)快四敞，超過(guò)了100%的提交：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        res, f, i, m = 0, 0, -1, {}
        for v in s:
            i = i+1
            if v in m and m[v]>=f:
                if res<i-f:
                    res= i-f
                f = m[v] + 1
            m[v] = i
        if res < i+1-f:
            res=i+1-f
        return res

再來(lái)一個(gè)非常容易理解的實(shí)現(xiàn)：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        d, res, start, = {}, 0, 0
        for i, v in enumerate(s):
            if v in d:
                # update the res
                res = max(res, i-start)
                # here should be careful, like "abba"
                start = max(start, d[v]+1)
            d[v] = i
        # return should consider the last
        # non-repeated substring
        return max(res, len(s)-start)

這道求最長(zhǎng)無(wú)重復(fù)子串的題和之前那道 Isomorphic Strings 很類似泛源，屬于LeetCode的早期經(jīng)典題目，博主認(rèn)為是可以跟Two Sum媲美的一道題忿危。給了我們一個(gè)字符串俩由，讓我們求最長(zhǎng)的無(wú)重復(fù)字符的子串，注意這里是子串癌蚁，不是子序列幻梯，所以必須是連續(xù)的。我們先不考慮代碼怎么實(shí)現(xiàn)努释，如果給一個(gè)例子中的例子"abcabcbb"碘梢，讓你手動(dòng)找無(wú)重復(fù)字符的子串，該怎么找伐蒂。博主會(huì)一個(gè)字符一個(gè)字符的遍歷煞躬，比如a，b逸邦，c恩沛，然后又出現(xiàn)了一個(gè)a，那么此時(shí)就應(yīng)該去掉第一次出現(xiàn)的a缕减，然后繼續(xù)往后雷客，又出現(xiàn)了一個(gè)b，則應(yīng)該去掉一次出現(xiàn)的b桥狡，以此類推搅裙，最終發(fā)現(xiàn)最長(zhǎng)的長(zhǎng)度為3皱卓。所以說(shuō)，我們需要記錄之前出現(xiàn)過(guò)的字符部逮，記錄的方式有很多娜汁，最常見(jiàn)的是統(tǒng)計(jì)字符出現(xiàn)的個(gè)數(shù)，但是這道題字符出現(xiàn)的位置很重要兄朋，所以我們可以使用HashMap來(lái)建立字符和其出現(xiàn)位置之間的映射掐禁。進(jìn)一步考慮，由于字符會(huì)重復(fù)出現(xiàn)颅和，到底是保存所有出現(xiàn)的位置呢穆桂，還是只記錄一個(gè)位置？我們之前手動(dòng)推導(dǎo)的方法實(shí)際上是維護(hù)了一個(gè)滑動(dòng)窗口融虽，窗口內(nèi)的都是沒(méi)有重復(fù)的字符享完，我們需要盡可能的擴(kuò)大窗口的大小。由于窗口在不停向右滑動(dòng)有额，所以我們只關(guān)心每個(gè)字符最后出現(xiàn)的位置般又，并建立映射。窗口的右邊界就是當(dāng)前遍歷到的字符的位置巍佑，為了求出窗口的大小茴迁，我們需要一個(gè)變量left來(lái)指向滑動(dòng)窗口的左邊界，這樣萤衰，如果當(dāng)前遍歷到的字符從未出現(xiàn)過(guò)堕义，那么直接擴(kuò)大右邊界，如果之前出現(xiàn)過(guò)脆栋，那么就分兩種情況倦卖，在或不在滑動(dòng)窗口內(nèi)，如果不在滑動(dòng)窗口內(nèi)椿争，那么就沒(méi)事怕膛，當(dāng)前字符可以加進(jìn)來(lái)，如果在的話秦踪，就需要先在滑動(dòng)窗口內(nèi)去掉這個(gè)已經(jīng)出現(xiàn)過(guò)的字符了褐捻，去掉的方法并不需要將左邊界left一位一位向右遍歷查找，由于我們的HashMap已經(jīng)保存了該重復(fù)字符最后出現(xiàn)的位置椅邓，所以直接移動(dòng)left指針就可以了柠逞。我們維護(hù)一個(gè)結(jié)果res，每次用出現(xiàn)過(guò)的窗口大小來(lái)更新結(jié)果res景馁，就可以得到最終結(jié)果啦板壮。

這里我們可以建立一個(gè)HashMap，建立每個(gè)字符和其最后出現(xiàn)位置之間的映射裁僧，然后我們需要定義兩個(gè)變量res和left个束，其中res用來(lái)記錄最長(zhǎng)無(wú)重復(fù)子串的長(zhǎng)度，left指向該無(wú)重復(fù)子串左邊的起始位置的前一個(gè)聊疲，由于是前一個(gè)茬底，所以初始化就是-1，然后我們遍歷整個(gè)字符串获洲，對(duì)于每一個(gè)遍歷到的字符阱表，如果該字符已經(jīng)在HashMap中存在了，并且如果其映射值大于left的話贡珊，那么更新left為當(dāng)前映射值最爬。然后映射值更新為當(dāng)前坐標(biāo)i，這樣保證了left始終為當(dāng)前邊界的前一個(gè)位置门岔，然后計(jì)算窗口長(zhǎng)度的時(shí)候爱致，直接用i-left即可，用來(lái)更新結(jié)果res寒随。

這里解釋下程序中那個(gè)if條件語(yǔ)句中的兩個(gè)條件m.count(s[i]) && m[s[i]] > left糠悯，因?yàn)橐坏┊?dāng)前字符s[i]在HashMap已經(jīng)存在映射，說(shuō)明當(dāng)前的字符已經(jīng)出現(xiàn)過(guò)了妻往，而若m[s[i]] > left 成立互艾，說(shuō)明之前出現(xiàn)過(guò)的字符在我們的窗口內(nèi)，那么如果要加上當(dāng)前這個(gè)重復(fù)的字符讯泣，就要移除之前的那個(gè)纫普，所以我們讓left賦值為m[s[i]]，由于left是窗口左邊界的前一個(gè)位置（這也是left初始化為-1的原因，因?yàn)榇翱谧筮吔缡菑?開(kāi)始遍歷的），所以相當(dāng)于已經(jīng)移除出滑動(dòng)窗口了讹开。舉一個(gè)最簡(jiǎn)單的例子"aa"谁尸，當(dāng)i=0時(shí)，我們建立了a->0的映射懦趋，并且此時(shí)結(jié)果res更新為1，那么當(dāng)i=1的時(shí)候，我們發(fā)現(xiàn)a在HashMap中但指，并且映射值0大于left的-1，所以此時(shí)left更新為0抗楔，映射對(duì)更新為a->1棋凳，那么此時(shí)i-left還為1，不用更新結(jié)果res连躏，那么最終結(jié)果res還為1