3.无重复字符的最长子串(Medium)

题目描述

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

样例

Input: "abcabcbb"
Output: 3 
# 解释 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

题解

参考 这个图文教程

​ 建立一个256位大小的整型数组freg，用来建立字符和其出现位置之间的映射。维护一个滑动窗口，窗口内的都是没有重复的字符，去尽可能的扩大窗口的大小，窗口不停的向右滑动。

（1）如果当前遍历到的字符从未出现过，那么直接扩大右边界； （2）如果当前遍历到的字符出现过，则缩小窗口（左边索引向右移动），然后继续观察当前遍历到的字符； （3）重复（1）（2），直到左边索引无法再移动； （4）维护一个结果res，每次用出现过的窗口大小来更新结果res，最后返回res获取结果。

Python示例

使用 辅助数组 作为访问记录

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        visited = {} # 辅助数组
        for char in s:
            visited[char] = 0
        l, r = 0, -1 
        maxSubString = 0
        while l < len(s):
            if r + 1 < len(s) and not visited[s[r + 1]]:
                r += 1
                visited[s[r]] = 1
                maxSubString = max(maxSubString, r - l + 1) # 只有右扩的话才有意义
            else:
                visited[s[l]] -= 1
                l += 1
        return maxSubString

使用 集合 作为访问记录

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l, r = 0, -1
        ans = 0
        visited = set() # 集合
        while l < len(s):
            if r + 1 < len(s) and s[r + 1] not in visited:
                r += 1
                visited.add(s[r])
            else:
                visited.remove(s[l])
                l += 1
            ans = max(ans, r - l + 1)
        return ans