LeetCode 3. Longest Substring Wi

3. Longest Substring Without Repeating Characters

题目

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

Example 1:

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 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.

知识点

1. 错误解法：这种解法得到的是从第一个非重复字符开始的最长字串。

# -*- coding: utf-8 -*-
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0
        temp_length = 0
        old_word = set()
        # 对每一个字母
        # 1 如果之前出现过， 则判断temp_length是否大于max_length，set.clear，temp_length = 1 ，加入到set中。
        # 2 如果之前没出现过，则temp_length ++ ，加入到set中
        # 退出循环后， 判断temp_length是否大于max_length
        for i in s:
            if i in old_word:
                max_length = max(temp_length, max_length)
                old_word.clear()
                temp_length = 1
                old_word.add(i)
            else:
                temp_length += 1
                old_word.add(i)

        max_length = max(temp_length, max_length)
        return max_length


solution = Solution()
assert solution.lengthOfLongestSubstring("") == 0
assert solution.lengthOfLongestSubstring(" ") == 1
assert solution.lengthOfLongestSubstring("asc") == 3
assert solution.lengthOfLongestSubstring("aasc") == 3
assert solution.lengthOfLongestSubstring("bbbb") == 1
assert solution.lengthOfLongestSubstring("abcabcbb") == 3

assert solution.lengthOfLongestSubstring("dvdf") == 3 # 当出现重复字母时，clear时把需要的字串也去掉了

2. 暴力方法，遍历所有子串，然后写个函数判断是否为不含重复字符子串，然后找最长的那个，复杂度为O(N^3)，会超时

    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0
        def check_unique(ss):
            old_word = set()
            for sss in ss:
                if sss in old_word:
                    return False
                old_word.add(sss)
            return True

        for i in range(0, len(s)):
            temp_s = s[i:]
            for j in range(0, len(temp_s) + 1):
                sub_s = temp_s[:j]
                if check_unique(sub_s):
                    max_length = max(max_length, len(sub_s))
        return max_length

解题 1

3. 分析一下暴力方法的缺点和优化：

• 每次判断字串是否为非重复，都需要遍历一遍字符串，复杂度为O(N)，但实际上如果字串中只多加了一个字符，这个新的字串只需要O(1)的复杂度就可以判断是否为非重复字串。
• 为了利用这个特点，我们使用滑动窗口的方法遍历子串，对于字符串或者数组，用下标[i,j)表示窗口.[i,j+1)表示窗口向右扩大1，[i+1,j+1)表示窗口右移。
• 遍历方法为：i从0到len(s)-1, j从i到len(s)-1，每次判断s[j]是否在set中，复杂度为O(n^2)
• 同时注意到，如果s[j]是否在set中，则以i为左窗口的字串最长长度就是j-i了，此时可以i++
• 最终答案为“以i为左窗口的最长子串”

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0
        for i in range(0, len(s)):
            set_start_from_i = set()
            j = i
            while j < len(s):
                if s[j] in set_start_from_i:
                    break
                else:
                    set_start_from_i.add(s[j])
                    j += 1
            max_length = max(max_length, j - i)
        return max_length

解题 2

4. 同样的原因，在每次s[j] in set,要更新i（右移左窗口）的时候，其实不需要把set清零。发现因为如果想把s[j]包含进来，必须不断左移i（set.pop(s[i]), i++），直到s[j] not in set。复杂度O(n)

• 算法总结如下：
  1. i，j代表左右窗，set代表窗中的内容，要求窗中内容没有重复的，求最大窗。
  2. 从0开始，j=i，先j向右扩张，while(j<=len(s) and s[j] not in set):set.add(s[j]), j++ 。当结束的时候，说明要么到了最右端要么就不能再扩张了，此时长度j-i是以i为左端点时的最大窗口。
  3. 此时如果j==len(s)说明已经到最后了，可以结束，因为此时就是最长了。
  4. 之后找下一个i，while(i<len(s) and s[j] in set): set.pop(s[i]), i++

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = 0
        j = 0
        window_content = set()
        max_len = 0
        
        while i < len(s):
            while j < len(s) and s[j] not in window_content:
                window_content.add(s[j])
                j += 1
            max_len = max(max_len, (j - i))
            if j == len(s):
                break
            else:
                while i < len(s) and s[j] in window_content:
                    window_content.remove(s[i])
                    i += 1
        return max_len