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

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

写个时间复杂度是 O(n^2) 的暴力，过了但是只击败了 5% 的用户。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        ans = 1
        for i in range(n):
            now_length = 1
            seen = set()
            seen.add(s[i])
            for j in range(i+1, n):
                if s[j] not in seen:
                    seen.add(s[j])
                    now_length += 1
                    ans = max(now_length, ans)
                else:
                    break
        return ans

用滑动窗口的思想进行优化，一般来说，滑动窗口类型的题目可以模板化为这样的代码：

for i in range(n):
    window = set()
    while right < n and (window not in valid):
        window.add(s[right])
        right += 1
    ans = max(ans, right - i)
    window.remove(s[i])

滑动窗口的时间复杂度是 O(n)。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        if n == 1:
            return 1
        seen = set()
        right = 0
        ans = 0
        for i in range(n-1):       
            while right < n and s[right] not in seen:
                seen.add(s[right])
                right += 1
            ans = max(ans, right - i)
            seen.remove(s[i])
        return ans