Leetcode 3. Longest Substring Wi

找到给定字符串中最长的没有重复的子字符串。
例子：
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
我的o(n^2)算法：
让left = 0，right = 0，maxlenght = 0，然后right依次向后扫描，建一个dictionary，key为扫描过的字符，value为位置，如果没有right指向的字符没有在dictionary里面，就放进去然后right继续向后，如果在dictionary里面则将left指定到重复字符位置+1， 重新调整dictionary， 直到right到达最➡️。
python代码：

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s) == 0:
            return 0
        res = 0
        left = 0
        right = 0
        hashset = {}
        while right < len(s):
            while right < len(s) and s[right] not in hashset:
                hashset[s[right]] = right
                right += 1
                
            if right < len(s) and s[right] in hashset:
                if hashset[s[right]] >= left:
                    res = max(res, right-left)
                    left = hashset[s[right]] + 1
                hashset[s[right]] = right
                right += 1
        res = max(res, right-left)
        return res
                 
        

看别人的o(n)算法，太厉害了吧。
设置start和maxlength都为0，useddict 为用过的字符。for loop从左向右循环，如果字符在dictionary里没出现过，则更新maxlength，如果字符在dictionary中出现过，并且start在字符位置之前，那么更新start在出现字符之后一位。
python代码：

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start = maxlength = 0
        useddict = {}
        for i in range(len(s)):
            if s[i] in useddict and start <= useddict[s[i]]:
                start = useddict[s[i]] + 1
            else:
                maxlength = max(maxlength, i - start + 1)
            useddict[s[i]] = i
        return maxlength