Longest string without duplicate characters

One . Problem description

Given a string s , Please find out that there are no duplicate characters in it Longest substrings The length of .

Example 1:
Input : s = “abcabcbb”
Output : 3
explain : Because the longest substring without repeating characters is “abc”, So its length is 3.

Example 2:
Input : s = “bbbbb”
Output : 1

Example 3:
Input : s = “pwwkew”
Output : 3

Example 4:
Input : s = “”
Output : 0
For details, see links. : The longest string without duplicate characters .

1. Thinking about this problem

First get the question , With “abcabcbb” String for example , First step , First define a variable i, Traverse from head to tail , It takes a cycle .
The second step , You also need to define a variable j, stay i Move back on the basis of , Means to move backward j position , At this time, the position of the station is s[i+j], Another cycle , How to ensure backward movement j Behind you （ Add a new character ）,i To i+j There is no string between and j Characters repeat ？
The third step , I need one more variable k, from i Loop to i+j-1, Observe whether there are and j The same characters .
So far, the idea of this problem is relatively clear , A total of three cycles are required .

2. Step one

int i=0; // Start traversing from the first one on the left 
while(s[i]){
     // When the first i String is not empty 
	/* The middle operation */
	i++;
}

3. Step two

int j = 1; //j stay i On the basis of 1, It's from i The next one starts walking 
while(s[i+j]){
    
	/* The middle operation */
	if( Repeat )// If there are duplicate characters ,
		break;// Just jump out of this cycle , This one is useless ,j There is no need to add , Go to step one and add i, Start the next round j The traversal 
	j++;
}

4. Step three

int k = 0, flag = 0;// From i Bit start , With the newly added i+j Bit judgment , So initialization 0
while(k < j){
    // Only judge i To i+j Characters between 
	if(s[i+j] == s[i+k]){
     // Equal to exit the loop 
	flag = 1;// A sign with repeated characters 
	break;
	}
	k++;// Otherwise, continue to search later 
}

5. Merge

int i = 0, len = 0;
    while(s[i]){
    
        int j = 1;  
        while(s[i + j]){
    
            int k = 0, flag = 0;
            while(k < j){
    
                if(s[i + j] == s[i + k]){
    
                    flag = 1;
                    break;
                }
                k++;
            }
            if(flag)
                break;
            j++;
        }
        if(j > len)
            len = j;
        i++;
    }
    return len;

6. Running results

It's really stretching , It took too long , Memory is OK . Now think about whether our program is optimized ？

Two . Slide window optimization

1. Slide the window to explain

According to the description of the problem solution , Set a window , The subscript on the left side of the window is i, The right subscript is j, At first it must be i=j=0, The window has only the first character .
First step , hold j To the right , Judge this j And the characters in the window （i ~ j-1） Is there the same , If you don't continue to move right .（ Notice the j It's different from the previous one , This j It's the right border of the window , The previous chapter, j It's relative to i, turn right j Step ）.
The second step , If the previous step is repeated , Come here to ： hold i Move one bit to the right , Once again, judge whether there is and... In the window j Bit repeated , If there is ,i Keep moving right , Until there is no reset , Out of the loop .
The third step , After jumping out , You can take the length ,len=max(max, j-i+1). Then proceed to step one .

2. Program

Copy the official answer of Li Kou .

//  Hash set , Record whether each character appears 
        unordered_set<char> occ;
        int n = s.size();
        //  Right pointer , The initial value is  -1, It's like we're on the left side of the left bound of the string , It's not moving yet 
        int rk = -1, ans = 0;
        //  Enumerate the position of the left pointer , The initial value is implicitly expressed as  -1
        for (int i = 0; i < n; ++i) {
    
            if (i != 0) {
    
                //  The left pointer moves one space to the right , Remove a character 
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
    
                //  Keep moving the right pointer 
                occ.insert(s[rk + 1]);
                ++rk;
            }
            //  The first  i  To  rk  A character is a very long non repeating character substring 
            ans = max(ans, rk - i + 1);
        }
        return ans;

 author ：LeetCode-Solution
 link ：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

3. The illustration

First step , There is only one
The second step ,j Moves to the right one
The third step ,j Moves to the right one
Step four ,j Moves to the right one
Step five ,j Moves to the right one , Join in s[4] The value is b, Before traversing, I found that there is b, be i Moves to the right one , I found that there was , Move right again , Until the s[1] Ruled out .
Step six , Before traversing, I found that there is b, be i Moves to the right one ,
Step seven , Traversing the previous string again, I found that there is b, be i Moves to the right one ,
Step eight ,j Moves to the right one ,
Step nine , Before traversing, I found that there is c, be i Moves to the right one ,
Step 10 ,j Moves to the right one
Step 11 , Before traversing, I found that there is b, be i Moves to the right one ,
The twelfth step , Traversing the previous string again, I found that there is b, be i Moves to the right one ,
Thirteenth Step ,j Moves to the right one
The fourteenth step , Before traversing, I found that there is b, be i Moves to the right one ,
The fifteenth step , Traversing the previous string again, I found that there is b, be i Moves to the right one ,
The sixteenth step , end .

3、 ... and 、 To optimize the

There are invalid operations in the above legend , For example, step five , Learn about the new s[4] There is repetition with inside ,i Step by step , We know , stay i Before reaching the repeating element , This string of characters is invalid , So is there any way to directly locate the position of repeated characters , Start traversing from the next position of this position , namely i Equal to the next digit of the repeating character ： Skip to step 7 , from i=2.

1. Detailed steps

Three cycles ：
First step , First define a variable i, Traverse from head to tail , It takes a cycle .
The second step , You also need to define a variable j, Represents the right boundary of the string , Move one space at a time .
The third step , I need one more variable k, from i Loop to j-1, Observe whether there are and j The same characters ,k from 0 Start to j-1 end .

2. The illustration

Analyze by yourself according to the previous process .

3. A detail

Every time j Move , There will be a len, If i The remaining characters are less than len, Then there is no need to judge , Because even if the following is not repeated , It doesn't add up to more than len. So the final diagram is as follows ：

4. Show your code

int i = 0, len = 0, j = 1;
    while(s[i]){
    
        int k = 0;
        while(s[j]){
    
            int flag = 0;
            while((i + k) < j){
    
                if(s[j] == s[i + k]){
    
                    flag = 1;
                    break;
                }
                k++;
            }
            if(flag)
                break;
            j++;
            k = 0;
        }
        if((j - i) > len)
            len = j - i;
        i = i + k + 1;
        if((i + len) > s.size())
            break;
        j++;
    }
    return len;

effect ：

Four 、 Last

There is really no way to optimize , Friends with better ideas can leave messages, chat privately and study together . Just started to brush algorithm problems , Record the process of thinking .