LeetCode 3 [Longest Substring Wi

原题

给定一个字符串，请找出其中无重复字符的最长子字符串。

样例
例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为 3。
对于，"bbbbb"，其无重复字符的最长子字符串为"b"，长度为1。

解题思路

• 窗口类问题 - 最自然的方法双层for循环，时间复杂度O(n2)解决
• 考虑优化 - 即那些状态不需要扫描呢？以"abcbcbb"为例
• 第一：left = 0, right = 3时出现重复，则right = 4, 5, ...都不需要在考虑，直接退出while循环
• 第二：上一步退出循环以后，下一个i从哪里开始？从left = 1开始吗？错。由于hashmap记录了每一个字母出现的位置，所以right = 3时，字母是b，导致了重复，所以i可以直接从上一个b出现的位置的下一个开始，本例中即left = 2，才能保证开始是合法的。
• 最后的时间复杂度是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)):
            # 如果出现重复，更新合法子串的左边界
            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