#title#Longest Substring Without Repeating Characters #description:#Given a string, #find the length of the longest substring without #repeating characters. For example, #the longest substring without repeating letters #for "abcabcbb" is "abc", which the length is 3. #For "bbbbb" the longest substring is "b", #with the length of 1.# one method:O(n)# dict.has_key need O(1)# substring forward a bit each step# class Solution:#     # @return an integer#     def lengthOfLongestSubstring(self, s):#     	substring = dict()#     	max_len = 1#     	min_num = 0#     	for i in range(len(s)):#     		if not substring.has_key(s[i]):#     			substring[s[i]] = i #     			if (i + 1 - min_num > max_len):#     				max_len = i + 1 - min_num#     		else:#     			if(substring[s[i]] + 1 > min_num):#     				min_num = substring[s[i]] + 1#     			if(substring[s[i]] < min_num):#     				substring[s[i]] = min_num#     			if(i - substring[s[i]] > max_len):#     				max_len = i -substring[s[i]]#     			substring[s[i]] = i #     		print max_len,min_num,substring#     	return max_len#method two:need O(n)#add flag to fore_process #and note that print sentenceclass Solution:    # @return an integer    def lengthOfLongestSubstring(self, s):    	substring = dict()    	max_len = 1    	min_num = 0    	flag = dict()    	for i in range(len(s)):    		flag[s[i]] = 0    	for i in range(len(s)):    		if flag[s[i]] == 0:    			flag[s[i]] = 1    			substring[s[i]] = i     			if (i + 1 - min_num > max_len):    				max_len = i + 1 - min_num    		else:    			if(substring[s[i]] + 1 > min_num):    				min_num = substring[s[i]] + 1    			if(substring[s[i]] < min_num):    				substring[s[i]] = min_num    			if(i - substring[s[i]] + 1 > max_len):    				max_len = i + 1 - substring[s[i]]    			substring[s[i]] = i     		# print max_len,min_num,substring    	if len(s) == 0:    		max_len = 0    	return max_lenif __name__ == ‘__main__‘:	s = Solution()	substring = ‘abcabcbb‘	substring = ‘bbbbb‘	substring = ‘abcabbcaa‘	substring = ‘ynqogshxhchhpqhjrwwtdm‘	substring = ‘bhhoejpnsoqioadvynqrbo‘#	substring = ‘‘#	substring = ‘tmmzuxt‘	print s.lengthOfLongestSubstring(substring)