-
Given a string, find the length of the longest substring without repeating characters.
-
Examples:
-
Given
"abcabcbb"
, the answer is"abc"
, which the length is 3. -
Given
"bbbbb"
, the answer is"b"
, with the length of 1. -
Given
"pwwkew"
, the answer is"wke"
, with the length of 3. Note that the answer must be a substring,"pwke"
is a subsequence and not a substring.
- 遍历字符串,过程中将出现过的字符存入字典,key为字符,value为字符下标
- 用maxLength保存遍历过程中找到的最大不重复子串的长度
- 用start保存最长子串的开始下标
- 如果字符已经出现在字典中,更新start的值
- 如果字符不在字典中,更新maxLength的值
- return maxLength
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = maxLength = 0
usedChar = {}
for i in range(len(s)):
if s[i] in usedChar and start <= usedChar[s[i]]:
start = usedChar[s[i]] + 1
else:
maxLength = max(maxLength, i - start + 1)
usedChar[s[i]] = i
return maxLength