# 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