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

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

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

解题思路：

1. 最初的思路是采用笨办法，也就是暴力的列出所有子串，判断各个子串是否满足“不含重复字符”的条件，如果满足则记录字符串长度。从最长的子串开始搜索，一旦出现满足条件的子串，就返回结果。
   采用以上方法的时间复杂度为O(n^3)，最终在某些测试样例上运行超时。

2. 借鉴其它的思路，可以只遍历一次字符串的各个字符，记录当前最长子串的长度，同时记录当前子串的起始位置，遍历完成后即可得最终结果。使用这种方法时，不仅要用到各个字符的value，还需要用到对应的index，充分用到所有相关信息。时间复杂度为O(n)。

笨办法：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        n=len(s)
        if n==0:
            return 0
        for l in range(n,0,-1):
            for i in range(0,n-l+1,1):
                d={}
                for j in s[i:i+l]:
                    if d.get(j):
                        d[j]+=1
                    else:
                        d[j]=1
                if max(d.values())==1:
                    return l

更快速的方法：

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        start=0#当前子串的起始位置
        lmax=0#当前最大的子串长度
        d={}#用于记录value和index之间的映射
        for i,v in enumerate(s):
            # v in d表示此前出现过相同的字符，需要重新指定start
            if v in d:
                start=max(d[v]+1,start)
            # 记录当前各个字符对应的最大index
            d[v]=i
            # 得到当前最大的子串长度
            lmax=max(lmax,i-start+1)
        return lmax