python算法题之《给定一个字符串，请你找出其中不含有重复字符的“最长子串”的长度》
题目要求
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
代码及解析
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 字典用来存放当前字母在位置（从1开始）
dic = {}
# 最大子串长度
ans = 0
# flag为标志位，即当前未重复的起始值
flag =0
for i in range(len(s)):
# 若当前字符已经存在于字典的键中
if s[i] in dic:
# 返回当前字母对应的位置与flag中较大值作为flag为重复起始值，不让起始值变小
flag = max(dic[s[i]],flag)
# 计算未重复的值
ans = max(i-flag+1, ans)
# 将当前字符的位置存于字典中
dic[s[i]] = i+1
return ans
