无重复字符最长子串
题目地址：无重复字符最长子串
题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路
遍历字符串每个字符时，计算以该字符结束的不含重复字符子串的起始位置i，用该位置减去起始位置便是以该字符结束的最长不重复子串的长度。选取所有字符的该数值中最大的。
起始位置i的计算方法：
设置一个<str,int> 类型的字典st，每遍历一个字符都将其当前位置保存进st。
每次遍历一个字符，查看st中有没有该字符，如果有，则证明前面有与当前字符重复的字符，则当前字符的i值设置为前面字符的index+1
以str: abcbc为例：
| index | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| str | a | b | c | b | c |
| 起始位置 i | 0 | 0 | 0 | 2 | 3 |
以该字符结束的不重复子串长度即index-i+1 |
1 | 2 | 3 | 2 | 2 |
| 该字符对应的最长不重复子串 | a | ab | abc | cb | bc |
特殊情况：
str: abba,即两个相同字符中间的子串，仍含重复字符,此时，发生重复时，不能将当前字符的i值设置为前面重复字符的index+1，而是max(前一个重复字符的index+1,i),即i的取值是一个非递减序列
| index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| str | a | b | b | a |
| 起始位置 i | 0 | 0 | 2 | 2,注意这里不能是前一个a的index+1=1,如果是，则以该字符结束的最长不重复子串为：bba，显然有重复字符 |
以该字符结束的不重复子串长度即index-i+1 |
1 | 2 | 1 | 2 |
| 该字符结束的最长不重复子串 | a | ab | b | ba |
代码
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 保存字符index的字典
st = {}
i, ans = 0, 0
for j in range(len(s)):
if s[j] in st:
# 需要取最大值，应对abba的情况
# i是截至j，以s[j]为最后一个元素的最长不重复子串的起始位置，即索引范围是[i,j]的子串是以元素j为最后一个元素的最长子串。
i = max(st[s[j]]+1, i)
# 字符串的长度即为字符串的结束位置j，减去起始位置i，加1
ans = max(ans, j - i + 1)
st[s[j]] = j
return ans
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 changzeyan@foxmail.com
