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 subsequenceand not a substring.
解法1: 参考自LeetCode题解3:Longest Substring Without Repeating Characters
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start=0
max_length=0
n=len(s)
sub_str=''
for end in range(n):
if s[end] not in sub_str:
sub_str+=s[end]
else:
max_length=max(max_length,len(sub_str))
while s[start]!=s[end]:
start+=1
start+=1
sub_str=s[start:end+1]
return max(max_length,len(sub_str))
解法2: 参考自LeetCode该题目提交中 sample 64 ms submission
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
chars = {}
begin = 0
result = 0
for i, c in enumerate(s, 1):
if (c in chars) and (chars[c] > begin):
begin = chars[c]
elif (i - begin > result):
result = i - begin
chars[c] = i
return result