1. Problem: give a string and find out the longest substring without repeated characters

The longest unrepeated substring of abcbc is abc length is 3

2. Method 1: Violence Law

We can find out each substring, and then find the longest substring without repeating characters. The method is simple and crude.

The code is as follows:

1 #include<stdio.h> 2 #include<string.h> 3 //Determine whether there are duplicate characters 4 int isRepeat(char*str,int start,int end) 5 { 6 int i; 7 for(i=start;i<end;i++) 8 { 9 if(str[i]==str[end]) 10 return i;//If a duplicate character is found, the index of that character is returned 11 } 12 return -1;//Otherwise return-1，Indicates that there are no duplicate characters 13 } 14 15 void findMaxSubString(char * str) 16 { 17 int i,j; 18 int n,m;//Subscript to record the beginning and end of the longest substring 19 int max=0;//Record the maximum length of no repetition character substring 20 int num=0;//Length of the current substring without repeating characters 21 int len=strlen(str);//Find the string length 22 //Start listing each substring 23 for(i=0;i<len;i++) 24 { 25 for(j=i+1;j<len;j++) 26 { 27 //Judging from i Start to j Is there a duplicate character between 28 if(isRepeat(str,i,j)!=-1) 29 { 30 //If there are duplicate characters 31 num=j-i;//Record the current substring length 32 if(num>max) 33 { 34 max=num;//Record the maximum length 35 n=i;//Start subscript 36 m=j-1;//Ending subscript because j Characters are repeated before 37 } 38 39 break;//There are repeating characters, end this cycle 40 } 41 } 42 } 43 //Output length and the string 44 for(i=n;i<=m;i++) 45 printf("%c",str[i]); 46 printf("\nthe max len is %d ",max); 47 } 48 49 int main() 50 { 51 char * str="abcdefghacbcnnmjklabak"; 52 findMaxSubString(str); 53 return 0; 54 }

Algorithm analysis, to traverse each substring, time complexity O(n^2), judge whether each substring has repetition, time complexity O(n),

So the whole time complexity O(n^3), which is very high, is not suitable for violence.

3. Method 2: sliding window

Sliding window is a common method in string processing. In short, window is a sequence maintained by itself. For string str, we already know from

The string from i to j has no repeating characters, so i to j is a window. Next, we need to determine whether the next character j+1 is repeated in the window, if not

Then J sliding j + + i remains the same. If i is repeated and slides to the next position of the repeating character, J continues to slide j + + forward. In this way, the longest unrepeated substring can be obtained when J is finished.

In fact, this method is to use the previously known information to judge, because we know whether the previous substring is repeated, and where it is repeated.

The code is as follows:

1 #include<stdio.h> 2 #include<string.h> 3 //Determine whether there are duplicate characters in the substring 4 int isRepeat(char*str,int start,int end) 5 { 6 int i; 7 for(i=start;i<end;i++) 8 { 9 if(str[i]==str[end]) 10 return i;//If a duplicate character is found, the index of that character is returned 11 } 12 return -1;//Otherwise return-1，Indicates that there are no duplicate characters 13 } 14 15 void findMaxSubString(char *str) 16 { 17 int len=strlen(str);//Get string length 18 int max=0;//Record the maximum length of unrepeated substring 19 int flag=0;// 20 int i=0,j=1; 21 int num=1;//Current no repeat substring length 22 int n,m;//Record the start and end subscripts of the largest unrepeated substring 23 // 24 while(j<len) 25 { 26 flag=isRepeat(str,i,j); 27 if(flag==-1)//flag by-1 No duplicate characters 28 { 29 j++;//j Slide forward 30 num++;//Add one to the length of current unrepeated substring 31 } 32 //There are duplicate characters 33 else 34 { 35 //If the current length is greater than the maximum length 36 if(num>max) 37 { 38 //Record subscript 39 n=i; 40 m=j-1; 41 max=num; 42 43 } 44 //i Start at the next position with repeating characters 45 i=flag+1; 46 j++;//j Continue to slide forward 47 num=j-i;//Current no repeat substring length 48 49 } 50 } 51 //Output length and the substring 52 for(i=n;i<=m;i++) 53 printf("%c",str[i]); 54 printf("\nthe max len is %d ",max); 55 } 56 int main() 57 { 58 char * str="abcdefghacbcnnmjklabak"; 59 findMaxSubString(str); 60 return 0; 61 }

In algorithm analysis, the sliding window is repeated, and the time complexity is O(n), plus the time complexity of judging whether the substring has repeated O(n), so

The time complexity is O(n^2). But in fact, most of the time to determine whether a substring has duplicate characters, not using my method above, but using a hash table, or a collection, the time complexity is O(1)

Therefore, the time complexity of this method is linear, in essence, O(n) is much better than violence method.