无重复字符的最长字串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路

给定一个串，使用while循环进行遍历，终止条件是while的查询索引找到最后一个字符。使用python中的in来判断字符是否在给定的串中。如果不在就添加到临时串中，如果在的话直接退出。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #初始化串和初始索引
        maxAllLen=0
        for i in range(len(s)):
            temp=s[i]
            maxLen=1
            for j in range(i+1,len(s)):
                if s[j] not in temp:
                    temp=temp+s[j]
                    maxLen+=1
                else:
                    break
            if maxAllLen<maxLen:
                maxAllLen=maxLen
        return maxAllLen

笨方法加1

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s or len(s)==1:
            return len(s)
        left,right=0,1
        begin,end=0,1
        while right<len(s):
            if len(set(s[left:right+1]))!=len(s[left:right+1]): #说明遇到了一样的
                print("hhhh")
                if right-left>end-begin:
                    begin=left
                    end=right
                    #处理left
                while s[left]!=s[right]:
                    left+=1
                left+=1
                print(f"{left}:{right}")
            right+=1
        if right+1-left>end-begin:
            return len(s[left:])
        else:
            return len(s[begin:end])

思路

来源于题解，使用的是滑动窗口的思路，如果移入了冲突的元素，就从头部位置将元素移除。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        #定义初始滑动窗口
        maxLen=0
        curLen=0
        left=0
        deque=set()
        for i in range(len(s)):
            #清除冲突元素
            while s[i] in deque:
                deque.remove(s[left])
                left+=1
                curLen-=1
            curLen+=1
            deque.add(s[i])
            if curLen>maxLen:
                maxLen=curLen
        return maxLen

滑动窗口的精髓就在于他有一个while的内部循环。

思路

最新写的代码，好像比第一次写的更好看一点

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left,right=0,1
        begin,end=0,1
        while right<len(s):
            if s[right] in s[left:right]:
                while s[left]!=s[right]:
                    left+=1
                left+=1
            else:
                right+=1
            if right-left>end-begin:
                end=right
                begin=left
        if end-begin>right-left:
            return len(s[begin:end])
        else:
            return len(s[left:])