leetcode 3. Longest Substring Without Repeating Characters 最长非重复子串的长度滑动窗口法

深碍√TFBOYSˉ_ 2022-05-26 10:15 217阅读 0赞

![这里写图片描述][70]  
[题目链接][Link 1]

根据我们之前介绍的滑动窗口法的解法:  
[滑动窗口法详解][Link 2]  
[leetcode 438. Find All Anagrams in a String 滑动窗口法][leetcode 438. Find All Anagrams in a String]  
这题，我们不难解决，使用之前的模板。可得如下解法

from collections import defaultdict
    
    class Solution:
        def lengthOfLongestSubstring(self, s):
            begin, end , counter, d = 0, 0, 0, 0
            map_dict = defaultdict(int)
            while end < len(s):
                c = s[end]
                map_dict[c] += 1
                # counter表示重复字符的个数
                if map_dict[c] > 1:
                    counter += 1
                end += 1
                # 将begin一直移到第一个重复字符的位置
                while counter > 0:
                    char_tmp = s[begin]
                    if map_dict[char_tmp] > 1:
                        counter -= 1
                    map_dict[char_tmp] -= 1
                    begin += 1
                # 每次计算下当前子串长度
                d = max(d, end - begin)
            return d

提供一种更短的解法：

class Solution:
        def lengthOfLongestSubstring(self, s):
            dic, res, start, = {}, 0, 0
            for i, ch in enumerate(s):
                if ch in dic:
                    start = max(start, dic[ch]+1)
                res = max(res, i-start+1)
                dic[ch] = i
            return res

[70]: /images/20220526/bf64f0e1cca54565a07f769bac6751c1.png
[Link 1]: https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
[Link 2]: https://blog.csdn.net/sty945/article/details/79846516
[leetcode 438. Find All Anagrams in a String]: https://blog.csdn.net/sty945/article/details/80103668