Leetcode 3 Longest Substring Without Repeating Characters

发表于 |

给定一个字符串，找出不含有重复字符的最长子串的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 无重复字符的最长子串是 “abc”，其长度为 3。

示例 2:
输入: “bbbbb”
输出: 1
解释: 无重复字符的最长子串是 “b”，其长度为 1。

示例 3:
输入: “pwwkew”
输出: 3
解释: 无重复字符的最长子串是 “wke”，其长度为 3。
请注意，答案必须是一个子串，”pwke” 是一个子序列 而不是子串。

题意分析：
在一个字符串中找最长子串(substring)，我们需要知道子串是连续的，而子序列(subsequence)是可以不连续的，这是两个不同的定义

思路分析：
通常对于这种在字符串中寻找最长XX的问题，都是使用双指针法。

我们首先固定左边，然后第二个指针向右遍历，使用一个空间记录我们已经访问过的元素，当第二个指针遍历到某个记录过的元素即停止，记录一次长度。

然后第一个指针向右移动，将遍历过的元素从记录中删除，直到完全删除掉第二个指针指向的元素为止。

例如对于示例1中的 ‘abcabcbb’，过程如图所示(只截取了一部分，后面同理)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 176ms, beats 18.11% (最初写的弱智解法反而运行时间更低，可能是初始化Counter()有点费时间)
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        i,j = 0,0
        # 使用d作为记录，等价于图中的vis
        d = collections.Counter()
        res = 0
        while i < len(s):
            while j < len(s) and s[j] not in d:
                d[s[j]] += 1
                j += 1
            res = max(res, j - i)
            if j >= len(s): break
            while i < len(s) and s[j] in d:
                d[s[i]] -= 1
                if d[s[i]] == 0: del d[s[i]]
                i += 1
        return res