3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

solution

• 滑动窗口/记录次数

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mydict = collections.defaultdict(int)
        l = 0
        res = 0
        for r, char in enumerate(s):
            mydict[char] += 1
            while mydict[char] > 1:
                mydict[s[l]] -= 1
                l += 1
            res = max(res, r - l + 1)
        return res

时间复杂度：O(n) 空间复杂度：O(1)

• 双指针/记录位置

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        mydict = {}
        start = 0
        res = 0
        for i, char in enumerate(s):
            if char not in mydict:
                dist = i - start + 1
                res = max(res, dist)

            else:
                if mydict[char] >= start:
                    start = mydict[char] + 1
                else:
                    res = max(res, i - start + 1)
            mydict[char] = i
        return res

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        left = 0
        res = 0
        for right, char in enumerate(s):
            pos = s.find(char, left, right)  # 维护一个dict来储存pos而不是每次都使用find来找
            if pos >= 0:
                left = pos + 1
            if right - left + 1 > res:
                res = right - left + 1
        return res

时间复杂度：O(n) 空间复杂度：O(1)