原题目

给定一个字符串，找出不含有重复字符的最长子串的长度。
示例：
给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是
给定 "bbbbb" ，最长的子串就是 "b" ，长度是1。
给定 "pwwkew" ，最长子串是 "wke" ，长度是3。请注意答案必须是一个子串，"pwke" 是 子序列 而不是子串。

思路

leetcode 不但要求算法正确 而且对算法有速度要求，因此这里不讨论暴力算法

• 1. 用一个字典保存在遍历时字符串中字符出现的最后位置
• 2. 用快慢指针标记不重复子串的开始和结束，开始搜索时，慢指针i=0，标记子串开始，快指针j标记子串结束
• 3. 移动j时，首先检测当前字符是否已经在字典中存有索引，如有检测到已经保存有索引并且索引值大于等于子串的起始位置I 则表明移动j时i和j之间出现了重复字符，此时对比子串长度，并保留大的子串长度。同时，将字串起始位置移动到当前字符上一次出现的位置之后
• 4. 每次循环最后更新字典中当前字符的索引值5 注意，循环结束后，j移出当前字符串，需要计算这最后一个不重复子串的长度

如上图所示：当检测到第二个b的出现位置时，第一个子串搜索结束，子串头指针移动到第一个b之后

代码

class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = 0
       
        maxlen = 1
        strslen = len(s)
        if strslen == 0:
            return 0
        j = i + 1
        dict1 = {}
        dict1[s[i]] = i
        index = -1
        while j < strslen:
            index = dict1.get(s[j],-1) #get this char's last found index, otherwise -1
            if index != -1 and index >= i:      #this char has been saved in dict and its index larger than i     
                maxlen = maxlen if maxlen > j -i else j-i #update maxlen
                i=index + 1 # move the start pointer i after the char's first occurence
            
            dict1[s[j]] = j #update char's latest index
            j += 1 # move j
        maxlen = maxlen if maxlen > j -i else j-i #after j move out of string, update maxlen again
        return maxlen