1.题目描述：

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

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

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

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

2.分析

• 这个问题首先想到的必定是暴力解法，那就是遍历两遍这个字符串，找到其中的所有子串，求得最长的子串长度。当然如果这么解的话，时间复杂度必然会达到让人难以接受的O(n2)。
• 利用滑动窗口的原理
• 首先设立一个字典last来保存所有字母最后出现的位置
• 接着设定一个指针left来保存最左边的合法位置，当if s[i] in last and last[s[i]]>= left:这个条件成立的时候，说明目前的子串中有相同字母，需要更新合法位置left,更新的值就是left = last[s[i]] + 1，代表排除上一个相同字符后，left的合法的位置
• 在python做算法题的时候，要时刻想着能否使用字典这个数据结构，来优化自己的算法，空间换时间

3.解决

• 暴力遍历法

class Solution:

    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        res_count = 0 # 最大结果
        res_str = '' # 最长字符串

        for i in range(len(s)):  # 循环这么多次  
            max_str = ''
            count = 0
            for j in s[i:]:
                if j not in max_str:
                    count += 1
                    max_str += j
                    if count > res_count:
                        res_count = count
                        res_str = max_str
                else:
                    break
        return res_count

• 滑动窗口法（利用字典hash表的查询优势）

class Solution(object):

    def lengthOfLongestSubstring(self, s):
        last = {}  # 保存每一个字母所在的最后位置
        left,ans=0,0  # left为保存当前合法位置
        
        for i in range(len(s)):
            if s[i] in last and last[s[i]]>= left:
                left = last[s[i]] + 1  # 当遍历到的字母存在在last字典当中，且字典中的值大于或者等于合法位置left，则加1
            last[s[i]] = i  # 更新字母最后出现的位置
            ans = max(ans,i-left+1)  # 更新最长子串，这个也是一个类似动态规划的问题
        return ans