[Med Bi-ptr模板] 3. Longest Substring Without Repeating Characters

Description

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

Solution

使用双指针做
T O(N)
s O(MIN(M,N)) M为char set个数
1同向双指针模板

class Solution:
    """
    @param s: a string
    @return: an integer
    """
    def lengthOfLongestSubstring(self, s):
        char_set = set()
        end = 0
        max_cnt=0
        for i in range(len(s)):
            while end < len(s) and s[end] not in char_set:
                char_set.add(s[end])
                end +=1
            max_cnt = max(max_cnt,end-i)
            char_set.remove(s[i])
        return max_cnt

2. 用dict存<char : pos>,有重复则update dict

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if len(s)==0:
            return 0
        cdict={}
        start =0
        end = 0
        s = list(s)
        max_cnt = 0
        while end < len(s):
            if s[end] not in cdict:
                cdict[s[end]]=end
                end +=1
            else:
                if max_cnt < len(cdict):
                    max_cnt = len(cdict)
                start = cdict[s[end]]+1
                for k,v in cdict.items():
                    if v < start:
                        del cdict[k]
                
        max_cnt = max(len(cdict),max_cnt)
        return max_cnt     
           ```