LeetCode-3 无重复字符串的最长子串

发表于 | 分类于 | 评论数： | 阅读次数：

题目：无重复字符串的最长子串

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

示例 1:

1
2
3
输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

1
2
3
4
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

思路

由于是在字符串中找无重复的子串，那么就可以用到set()类型。还是得遍历字符串，基本思路如下：

  • 初始化最长无重复子串长度record=0
  • 从头开始遍历字符串中的每一个字符
    • 初始化一个临时的li1=set()来存放子串
    • 判断当前字符是否存在于li1
      • 如果不存在就存入li1，并判断当前子串长度是否大于record，是则更新record
      • 如果存在，那么说明当前子串中有了重复字符，开始下一轮的查找

实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        record = 0
        for i in range(len(s)):
            li1 = set()
            for st in s[i:]:
                if st not in li1:
                    li1.add(st)
                    if len(li1) > record:
                        record = len(li1)
                else:
                    break
        return record

优化方法

在上述方法中，每当扎到一个重复字符时，就从下一个i开始重新遍历。我们可以在每个j的遍历过程中，记录下每个子字符串的index和值，并设置一个偏移量carry。如果j和j‘是重复字符，那么偏移量carry就等于i到j的长度，下一次遍历从i=i+carry+1即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
		record = 0
        i = 0
        while i < len(s):
            li1 = {}
            for j, char in enumerate(s[i:]):
                carry = 0
                if char not in li1:
                    li1[char] = j
                    carry += j
                    if len(li1) > record:
                        record = len(li1)
                else:
                    carry = li1[char]
                    break
            i = i + carry + 1
        return record

优化方法二

以上方法均需要做两层的循环，那么有没有只做一层循环的呢：

还是要用dict，我们需要寻找到两个下标i,j，使他们之间的长度最长，思路如下：

  • 初始化i = 0，最长无重复子串长度record=0，一个存放无重复字符串和对应index的dict：li1
  • 通过enumerate(s)的方式在遍历中获取每个字符char和其对应的index：j
    • 如果字符char不存在于li1，那么把char和j存入li1，更新record=max(record, j-i+1)
    • 如果字符char存在于li1，那么说明最长无重复子串需要从li1[char]后开始计算，即i=max(i,li1[char] + 1)

代码如下：

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        record = 0
        i = 0
        li1 = {}
        for j, char in enumerate(s):
            if char in li1:
                i = max(i, li1[char] + 1)
            record = max(record, j - i + 1)
            li1[char] = j
        return record

如果大家有更好的方法，欢迎一起探讨。