Longest substring without repeated characters (C language)

subject ： Given a string p, Please find out the length of the longest substring without repeating characters .

1 Violent solution

For an arbitrary string , To find its longest substring , It's easy to think of traversing each substring . The following code will traverse each substring , For one of the substrings , We also need to determine whether it satisfies the no repetition character .

Here the string length is len, The number of all non empty substrings is len!( Factorial ) individual , The time complexity of each judgment of whether there are no repeated characters is O(n²), So this algorithm is very slow . When the string length is very long , Basically no results .

#include <stdio.h>
#include <string.h>
int main(){
	int len, output=0, i, j, k, m, sub_status=1;
	char p[] = "aaabc";
	len = strlen(p);
	for(i=0;i<len+1;i++){
		for(j=0;j<len-i+1;j++){
			sub_status=1;
			for(k=j;k<j+i-1;k++){
				for(m=k+1;m<j+i;m++){
					if(*(p+k)==*(p+m)){
						sub_status=0;
						break;
					}		
				}
				if(sub_status==0)continue;
			}
			if(sub_status==1){
				output=i;
				break;
			}
		}
	}
	printf("%d", output);
}

2 Better way

The characters in the substring appear consecutively in the original string , This feature allows us to reduce “ Violence solution ” The overhead of determining whether there are repeated characters in the . We can put the elements in the queue one by one , After putting new elements , We determine whether there are duplicate characters in the original queue . If there is , Then discard this repeating character and all previous characters , Get a new queue , This keeps the queue free of duplicate elements . In the process , Each resulting new queue is a substring with no duplicate characters , We just compare their lengths and choose the longest one .

#include <stdio.h>
#include <string.h>
int main(){
	int len, output=0, i, j, head=0, tmp;
	char p[] = "jfdksliwi";
	len = strlen(p);
	for(i=1;i<len;i++){
		for(j=head;j<i;j++){
			if(*(p+j)==*(p+i)){
				head=j+1;
				break;
			}
		}
		tmp = i+1-head;
		if(tmp>output)
			output = tmp;
	}
	if(len-head>output)
		output = len-head;	
	printf("%d", output);
}