Table of Contents
Given a string, find the length of the longest substring without repeating characters.
"abcabcbb", the answer is “abc”, which the length is 3.
"bbbbb", the answer is “b”, with the length of 1.
"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.
My solution is using a list
temp to store the string and for each char in the
s, I check if this char has already been in
temp. If yes, then delete the substring before and including the char.
class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ length = 0 max_length = 0 temp =  for l in s: if l in temp: if len(temp) > max_length: max_length = len(temp) index = temp.index(l) temp = temp[index + 1:] length -= index + 1 temp.append(l) length += 1 return max(length, max_length)
The following code is from the submission using the smallest running time:
class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ long="" i=0 for x in s: if x not in long: long=long+x else: long=long.partition(x)+x if i<len(long): i=len(long) return i
This solution is better than mine in the following points:
- Use string
longinstead of a list
- Return a single value instead of a max function.
partitionbuilt-in function instead of list slice.
str.partition(sep) Split the string at the first occurrence of sep, and return a 3-tuple containing the part before the separator, the separator itself, and the part after the separator. If the separator is not found, return a 3-tuple containing the string itself, followed by two empty strings.