无重复字符串的最长子串

Leetcode Link: 3. 无重复字符的最长子串 - 力扣（LeetCode） (leetcode-cn.com) 剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）

题目

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

解法一

思路：滑动窗口，利用哈希表记录窗口内容，{"字符名字"：出现次数}

应该有两种方式统计哈希表内的窗口长度

• 当某一个字符的出现次数<0，删除该 item，直接统计 len(contents)
• 可以让某一个字符的出现次数<0，但是需要额外维护一个 curLength 的变量，随时指示当前的窗口长度

题解：自己的版本，感觉不优雅

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right = 0, 0 # 窗区间左闭右闭
        contents = {}      # 利用哈希表记录窗内内容
        res = 0            # 结果
        curLength = 0      # 当前窗内长度
 
        for right in range(len(s)):
            ## 入窗
            cur = s[right]
            curLength += 1
            if cur in contents: 
                contents[cur] += 1 # 出现次数 +1
            else: 
                contents[cur] = 1  # 没出现过，添加进来
            ## 判断是否需要出窗
            if contents[cur] > 1:
                ## 出窗
                while(1):
                    contents[s[left]] -= 1 # 出去的字符出现次数 -1
                    left += 1         # 左边界滑动
                    curLength -= 1    # 当前窗口长度维护
                    ## 直到重复的那个出去，就跳出
                    if contents[cur] == 1:
	                    break
            # 这里可以优化，因为它每步都跑一次
            # 想想，下面给出了答案
            res = max(res, curLength) 
        return res

代码优化

可以将结果更新放在出窗前，因为需要出窗的时候证明当前窗内有重复的了，所以更新一下 res = max(res, curLength-1) 同时为了避免字符串中一个重复的没有走不到出窗这一步，需要在返回res之前再更新一次 res = max(res, curLength)

解法二

思路：滑动窗口，利用队列记录窗口内容，能省两个指针

题解：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        q = collections.deque()
        res = 0
        for c in s:
            if c not in q:
                q.append(c) # 这个可以放在外面，因为来的c肯定要入窗。
            else:
                q.append(c)
                while(q.popleft()!=c):
                    continue
            res = max(res, len(q))
        return res

解法三

思路：滑动窗口，利用集合 set() 来做

题解：

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left = 0
        contents = set()
        res = 0
        cur_len = 0
        for val in s:
            cur_len += 1
            while val in contents:
                # 移除左指针元素
                contents.remove(s[left])
                left += 1
                cur_len -= 1
            res = max(cur_len, res)
            contents.add(val)
        res = max(cur_len, res)
        return res

解法四

思路 用哈希表做，使用 defaultdict

题解

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        dd = defaultdict(int)
        res = 0
        left = 0
        right = 0
        #[left, right)
        while(right<len(s)):
 
            while(dd[s[right]] != 0):
                dd[s[left]] -= 1
                left += 1
            
            dd[s[right]] += 1
            right += 1
            res = max(res, right - left)
 
        return res

解法五

请看题解学习使用动态规划的方法

启发和联系

集合 set() 的操作

• sets.add(val) 添加元素
• sets.remove(val) 移除元素
• vel in sets 是否存在某元素