3-无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

首先想到的就是遍历。

从头到尾，每一个位置i，都向后搜索到len(s)的位置，然后用一个set保存不重复的值，如果出现重复值则退出本次循环，重置一些状态，返回set中元素的个数，就是本次找到的最长子串。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        lenList = []
        currentLen = 0
        sss = set()
        for i in range(len(s)):
            for j in range(i, len(s)):
                if s[j] in sss:
                    lenList.append(currentLen)
                    currentLen = 0
                    sss.clear()
                    break
                else:
                    sss.add(s[j])
                    currentLen += 1
                    if j == len(s)-1:
                        lenList.append(currentLen)
                        currentLen = 0
                        sss.clear()
                        break
        return max(lenList) if len(lenList)!=0 else 0

显然，双层循环，时间复杂度为O(n²)

进阶（滑动窗口）

现在假设我们有一个可伸缩的长方形的框，初始长度是1，然后我们拿这个框，从头去套我们的字符串。

那么如果框中没有重复值，我们就更新最大长度，然后框的长度+1，如果加1后框中无重复值，则重复上述操作。最后返回最大值。

若果遇到重复值，则只要将我们的框，从上一个这个值出现的位置的后一位截取到最后，即可。

这样只需要进行一次遍历。时间复杂度为O(n)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s == "":
            return 0
        maxLen = 0
        currentLen = 1
        sss = []
        for i in s:
            if i not in sss:
                sss.append(i)
                maxLen = max(currentLen, maxLen)
            else:
                sss = sss[sss.index(i)+1:]
                sss.append(i)
                currentLen = len(sss)
            currentLen += 1
        return maxLen

O(n)的时间效率当然是比O(n²)高出不少的。