原題

給定一個(gè)字符串，請(qǐng)找出其中無(wú)重復(fù)字符的最長(zhǎng)子字符串。

樣例
例如，在"abcabcbb"中，其無(wú)重復(fù)字符的最長(zhǎng)子字符串是"abc"，其長(zhǎng)度為 3。
對(duì)于，"bbbbb"，其無(wú)重復(fù)字符的最長(zhǎng)子字符串為"b"，長(zhǎng)度為1。

解題思路

• 窗口類(lèi)問(wèn)題 - 最自然的方法雙層for循環(huán)，時(shí)間復(fù)雜度O(n2)解決
• 考慮優(yōu)化 - 即那些狀態(tài)不需要掃描呢？以"abcbcbb"為例
• 第一：left = 0, right = 3時(shí)出現(xiàn)重復(fù)，則right = 4, 5, ...都不需要在考慮，直接退出while循環(huán)
• 第二：上一步退出循環(huán)以后，下一個(gè)i從哪里開(kāi)始？從left = 1開(kāi)始嗎？錯(cuò)。由于hashmap記錄了每一個(gè)字母出現(xiàn)的位置，所以right = 3時(shí)，字母是b，導(dǎo)致了重復(fù)，所以i可以直接從上一個(gè)b出現(xiàn)的位置的下一個(gè)開(kāi)始，本例中即left = 2，才能保證開(kāi)始是合法的。
• 最后的時(shí)間復(fù)雜度是O(2n) => O(n)

完整代碼

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        left, res = 0, 0
        LastAppeared = {}
        for right in range(len(s)):
            # 如果出現(xiàn)重復(fù)，更新合法子串的左邊界
            if s[right] in LastAppeared and LastAppeared[s[right]] >= left:
                left = LastAppeared[s[right]] + 1
            LastAppeared[s[right]] = right
            res = max(res, right - left + 1)
        return res