Problem:
This system give you a long string,you should work out the longest substring without
repeating characters.
Such as :
Given "pwwkew", the answer is "wke", with the length of 3.
The first solution:
class Solution ( object ):
def Check ( self , tmp ):
char_set = set ( tmp )
if len ( tmp ) != char_set.__len__ ():
return {'answer': False , 'result': ''}
else:
return {'answer': True , 'result': char_set}
def lengthOfLongestSubstring ( self , s ):
length = len ( s )
flag = 0
for each in range ( length ):
for ebch in range ( each + flag , length ):
if ebch - each >= flag:
# print "%d\t%d" %(each,ebch)
# print s[each:ebch]
check = self.Check ( s[ each:ebch] )
# print check
if check[ 'answer' ] == True:
flag = ebch - each
for t in s[ ebch: ]:
if t not in check[ 'result' ]:
check[ 'result' ].add ( t )
flag += 1
else:
ebch = length - 1
break
else:
break
return flag
As what you have seen above,the first solution uses three layers of circulations.Thus,the sum of the consumption is O(n3). As for a long string, a long time is needed to work it out.
The second solution
class Solution ( object ):
def lengthOfLongestSubstring ( self , s ):
length = len ( s )
i = 0
j = 0
answer = 0
char_set = set ()
while i < length and j < length:
if s[ j ] not in char_set:
char_set.add(s[j])
j += 1
answer = max(answer,j - i)
else:
char_set.remove(s[i])
i += 1
return answer
As for the second methods,it uses a sliding windows to get the substring.In order to check whether the substring has repeating characters, set is a very essential tool according to its feature.
The sliding windows is the boundary of [i,j) (left-closed and right-opened ).When we check whether the substring s[i,j+1] has repeating characters, the result of substring s[i,j) which we have worked out is helpful. we only need to test whether s[j] is in the old set.
