Skip to main content

3. 无重复字符的最长子串 [medium]

3. 无重复字符的最长子串 [medium]​

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

image

Second Try​

2020-09-21

使用set和滑动窗口双指针解决。 

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) <= 1:
            return len(s)

        lft, rt = 0, 0 
        maxn = 0
        visited = set() 
        while rt < len(s):
            if s[rt] not in visited:
                visited.add(s[rt])
                maxn = max(maxn, rt - lft + 1)
                rt += 1
            else:
                while s[lft] != s[rt]: # 必然会出现除了rt之外的lft，使得s[lft] == s[rt]
                    visited.remove(s[lft])
                    lft += 1
                lft += 1 # 需要把s[lft] = s[rt]的lft挪动一位
                rt += 1 # 忘记导致出bug
        return maxn
  • 执行用时：96 ms, 在所有 Python3 提交中击败了40.82%的用户
  • 内存消耗：13.3 MB, 在所有 Python3 提交中击败了76.57%的用户

First Try​

2020-05-31

执行用时 :128 ms, 在所有 Python 提交中击败了25.00%的用户

内存消耗 :13 MB, 在所有 Python 提交中击败了6.06%的用户

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        longest = 0
        window = []
        for char in s:
            window.append(char)
            if(len(window) == len(set(window))):
                longest = max(longest, len(window))
            else:
                window.remove(window[0])
        return longest