Longest Substring Without Repeating Characters

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 2.1k | 阅读时长 ≈ 2 分钟

题目出处

源自于leetcode

题目描述

Given a string, find the length of the longest substring without repeating characters.

Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

解读

给定一个字串，返回最长不包含重复字符的子串。如"abcabcbb"的最长不包含重复字符的子串为“abc”,“bca”`等，长度都为3

第一版答案

思路

  1. 初始最长(max)不包含重复字符的子串为0，统计最长字串起始位置（start）为-1， 用data记录每个字符上一次出现位置；
  2. 遍历字符串，如果该字符没有出现（即不在data中），则迄今为止的最长长度为当前index - start;
  3. 否则，以当前字符结尾的最长字串肯定要从该字符上一次出现的位置算起。

举例"abcabcbb"

  1. 遍历a时，最长子串长度为1(“a”)；
  2. 遍历b时，最长子串长度为2(“ab”)；
  3. 遍历c时，最长子串长度为3(“abc”)；
  4. 遍历a时，由于a已经出现过一次，最长子串长度从第一位算起，则长度为3(“bca”)；
  5. ..

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        data = {}

        start = -1
        max = 0
        for index, char in enumerate(s):
            if char in data:
                start = data[char]
            data[char] = index
            len = index - start

            if max < len:
                max = len

        return max

第二版答案

缺陷

表现：当提交代码时，发现”abba”时错误了。
原因：

  1. start的值是我们认为统计以当前所遍历的字符结尾的最长字串的起始位置；
  2. 由于该题的特殊性质，start位置只能往后挪，不能往前挪，因为往前挪肯定会包含重复字符；
  3. 在处理”abba”时，第二个b，我们已经把start标记为第一个b的位置，而在处理第二个b时，我们把start往前挪了，所以正确答案应该为”ab”/“ba”，而我们得到了”bba”。

修改：
将if char in data: 修改为 if char in data and start < data[char]: 即可修复此bug。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        data = {}

        start = -1
        max = 0
        for index, char in enumerate(s):
            if char in data and start < data[char]:
                start = data[char]
            data[char] = index
            len = index - start

            if max < len:
                max = len

        return max

运行结果及效率

result

0%