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

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

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

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

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

解析：
这里的相关标签是：哈希表，字符串，双指针，sliding windows.
怎么理解？
首先，根据前两道题可以发现，这种寻找索引的题目，都会用到哈希表。其中，哈希表的key为数组的值，value则是索引。基本的思路是维持一个滑动窗，且窗内无重复字符，我们要做的是尽可能大的扩大窗口的大小。
以''为例：

这个滑动窗是通过左右两个指针来维持的，即左指针和右指针。
左指针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 这指针起始为， right 为当前字符索引。
'abba', 这种含有重复字符的字符串，left需要不断比较更新, 当新的字符与过去出现的字符重复，left为重复字符的上代索引.
>比如这个例子中运行到''时，left = -1，right 为当前字符索引，max_len = 2。
>当运行到''时，left = 1，right 为当前字符索引，max_len = 2。
但是这里其实包含一个小陷阱。
>当运行到''时，left = 0，right 为当前字符索引，则max_len = 3。
这是因为left在往前跳的时候，包含了重复的''。那么怎么解决这个问题呢？
就是在新的寻找left的值时多一层判断，即当运行到''时，上代的索引为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]] = rightif (right - left) > max_len: max_lin = right - leftreturn max_len