Daily LeetCode 3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Medium

问题描述

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.

题目分析：

给定一个字符串，要求输出最长的不包含重复字符的子串。注意是子串而不是子序列，因此一定要是连续的。

可以从我们自己的思考方式入手解决这个问题，以题中Example 1为例，当字符串为"abcabcbb"时，我们先从第一个字母a向后看，当遇到下一个a时，我们可以选择将已经找到的子串abc中的a去掉，此时最长子串变成了bca继续向后，遇到下一个b，同样，我们去掉b，此时最长子串变成了cab，以此类推，我们最终发现最长子串长度为3。

因此，我们需要一个dict来记录已遍历的字符出现的位置，在遍历过程中，不断更新dict内容。当遇到未出现过的字符时，我们只需要扩大子串长度即可；当遇到已经在dict中的字符时，我们需要一个变量来记录当前子串的最左位置，如果当前字符位置在子串中，为了保证没有重复元素，我们需要比较前后子串长度，保留较长的那个。

以Example 1为例：

leftPos: 0, ch_dict:{'a': 0}, max_length:1
leftPos: 0, ch_dict:{'b': 1, 'a': 0}, max_length:2
leftPos: 0, ch_dict:{'c': 2, 'b': 1, 'a': 0}, max_length:3
leftPos: 1, ch_dict:{'c': 2, 'b': 1, 'a': 3}, max_length:3
leftPos: 2, ch_dict:{'c': 2, 'b': 4, 'a': 3}, max_length:3
leftPos: 3, ch_dict:{'c': 5, 'b': 4, 'a': 3}, max_length:3
leftPos: 5, ch_dict:{'c': 5, 'b': 6, 'a': 3}, max_length:3
leftPos: 7, ch_dict:{'c': 5, 'b': 7, 'a': 3}, max_length:3

代码：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        leftPos, maxLength = 0, 0
        ch_dict = {}

        for index, ch in enumerate(s):
            if ch in ch_dict and leftPos <= ch_dict[ch]:
                leftPos = ch_dict[ch] + 1
            else:
                maxLength = max(maxLength, index - leftPos + 1)
        
            ch_dict[ch] = index
    
        return maxLength