【LeetCode】3. Longest Substring Without Repeating Characters 解题报告（Python），leetcoderepeating

【LeetCode】3. Longest Substring Without Repeating Characters 解题报告（Python）

标签（空格分隔）： LeetCode

作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/

---

题目地址：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目描述：

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

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", which the length is 3.

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: 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.

题目大意

找出字符串中最长的不含有重复字符的子串长度。

解题方法

看见题目求长度的，一般时间复杂度都不会太高。

解法一：使用set。

这个思路比较简单易懂，使用双指针，[left, right]来保存子串的左右区间，对应着这个区间我们维护一个set，这个set里面全部是不重复的字符。

使用while循环，如果right字符不在set中，就让它进去；如果right在，就把left对应的字符给remove出去。

所以，当我们得到一个right位置的字符时，通过移动left和修改[left,right]区间内对应的的set，来保持了一个最小的不重复字符区间。

比如：

a b c b b c b b
0 1 2 3 4 5 6 7

当right移动到3的时候字符时b，此时，set = {a, b, c}中，left=0，字符b在set中。

所以在while循环中反复移动left，当left移动到3的位置时，此时set = {c},字符b已经不在set中。

按照这个方式移动，set的个数最多的值即为最长子串。

一定注意：[left, right]区间和set是对应的，要同时维护。

代码如下：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        left, right = 0, 0
        chars = set()
        res = 0
        while left < len(s) and right < len(s):
            if s[right] in chars:
                if s[left] in chars:
                    chars.remove(s[left])
                left += 1
            else:
                chars.add(s[right])
                right += 1
                res = max(res, len(chars))
        return res

方法二：使用字典

使用字典保存每个字符第一次出现的位置。

当right向后遍历的过程中，如果这个字符在字典中，说明这个字符在前面出现过，即这个区间已经不是题目要求的不含重复字符的区间了，因此，需要移动left。

移动left到哪里呢？有个快速的方法，那就是移动到right字符在字典中出现的位置的下一个位置。

无论如何都会使用right更新字典，另外记录最大区间长度即为所求。

注意，left更新的时候需要保留最大（最右）的位置。举例说明：

对于abba，当right指向最后的a的时候，left指向的是字典中保留的有第一个位置的a，如果不对此进行判断的话，left会移动到第一个字符b。

left一定是向右移动的，不可能撤回到已经移动过的位置。

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        left, right = 0, 0
        res = 0
        chars = dict()
        for right in range(len(s)):
            if s[right] in chars:
                left = max(left, chars[s[right]] + 1)
            chars[s[right]] = right
            res = max(res, right - left + 1)
        return res

参考资料：https://www.youtube.com/watch?v=hw0zHamgaks

另外有个文章不错：http://www.cnblogs.com/grandyang/p/4480780.html

日期

2018 年 8 月 24 日 ———— Keep fighting!