[leetcode] 3.无重复字符的最长字串

难度：Medium.

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

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

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

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

解析：
这里的相关标签是：哈希表，字符串，双指针，sliding windows.

怎么理解？

首先，根据前两道题可以发现，这种寻找索引的题目，都会用到哈希表。其中，哈希表的key为数组的值，value则是索引。基本的思路是维持一个滑动窗，且窗内无重复字符，我们要做的是尽可能大的扩大窗口的大小。

以' $abcabcbb$ '为例：

$[a]bcabcbb$
$[ab]cabcbb$
$[abc]abcbb$
$abc[a]bcbb$
$ab[cab]cbb$
$abc[abc]bb$
$abcabc[b]b$
$abcabcb[b]$

这个滑动窗是通过左右两个指针来维持的，即左指针和右指针。
左指针left是该字符上次出现的位置；
右指针right则是该字符此次出现的位置。

字串的长度为right - left，最长字串的长度为max_len。
那么，当right - left > max_len时，更新max_len = right - left。

为了遍历每个字符，需要for循环：

for right in range(len(s)):

对于输入字符串有2种情况：

'a', 'b', ' ', 这种单字符的字符串，left 这指针起始为 $-1$ ， right 为当前字符索引。
'abba', 这种含有重复字符的字符串，left需要不断比较更新, 当新的字符与过去出现的字符重复，left为重复字符的上代索引.
>比如这个例子中运行到' $ab$ '时，left = -1，right 为当前字符索引 $1$ ，max_len = 2。
>当运行到' $abb$ '时，left = 1，right 为当前字符索引 $2$ ，max_len = 2。
但是这里其实包含一个小陷阱。
>当运行到' $abba$ '时，left = 0，right 为当前字符索引 $3$ ，则max_len = 3。
这是因为left在往前跳的时候，包含了重复的' $bb$ '。那么怎么解决这个问题呢？
就是在新的寻找left的值时多一层判断，即当运行到' $abba$ '时，上代 $a$ 的索引为0 $<$ 上代left = 1，这时不更新left。

代码：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_len = 0
        left = -1
        d = {}
        
        for right in range(len(s)):
            if s[right] in d and d[s[right]] > left:
                left  = d[s[right]]
            
            d[s[right]] = right
            
            if (right - left) > max_len:
                max_lin = right - left
        
         return max_len

最后编辑于：2020.02.20 10:27:08