Longest substring without repeating characters

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.

Tags: C

Posted on Fri, 03 Apr 2020 09:34:31 -0700 by powlouk