Sliding windows are divided into two types: unfixed window size and fixed window size: (commonly used when looking for substrings that meet certain requirements)

1) Unfixed window size: the window size will change. When the current window does not meet the requirements, it will move backward as a whole.

2) Fixed window size: the window size is a constant. When the current window does not meet the requirements, the whole window moves backward.

The difference between sliding window and double pointer is that the change direction of double pointer is bidirectional, which can be left pointer to the right or right pointer to the left, while sliding window moves the whole window to the right and the left and right pointers are synchronized.

1.3. Longest substring without repeated characters

Title Description:

Given a string ， s, please find out the length of the longest substring ， which does not contain duplicate characters.

Example:

Examples 1:
input: s = "abcabcbb"
output: 3 
explain: Because the longest substring without duplicate characters is "abc"，So its length is 3.

Example 2:
input: s = "bbbbb"
output: 1
 explain: Because the longest substring without duplicate characters is "b"，So its length is 1.

Example 3:
input: s = "pwwkew"
output: 3
 explain: Because the longest substring without duplicate characters is "wke"，So its length is 3.
     Please note that your answer must be the length of the substring,"pwke" It's a subsequence, not a substring.

Answer Description:

To find the length of the longest substring without repeated characters, the idea of sliding window is adopted.

Enumerate each character as the starting point of the string, find the longest string without repetition with this character as the starting point, stop immediately when there is repetition, and then move the left pointer of the sliding window to the right to continue enumerating the next string.

Because the characters in the sliding window must not be repeated, you only need to judge the characters outside the right window.

(note that in C + +, because STL has a container, unordered_set can be used for duplicate checking. When set.count==0, it means that the element is not repeated, and when set.count==1, it means that the element already exists in the container, which will cause duplication.)

code:

C + + sliding window:

class Solution {
public:
    int max(int a,int b)
    {
        return a>b?a:b;
    }
    int lengthOfLongestSubstring(string s) {
        int l=0;//Used to mark the starting position of the enumeration string
        int r=0;//Used to find the termination of the current enumeration string
        unordered_set<char> ss;//For weight removal
        int n=s.size();
        int max_str_len=0;
        int temp_len=0;//Used to record the longest substring length of the current enumeration string
        while(l<n)
        {  
            while(r<n && ss.count(s[r])==0)
            {
                ss.insert(s[r]);
                r++;
                temp_len++;
            }
            max_str_len=max(max_str_len,temp_len);  
            ss.erase(s[l]);
            temp_len--;
            l++;
            
        }
        return max_str_len; 
    }
};

C kmp algorithm:

//kmp algorithm
int max(int a,int b)
{
    return a>b?a:b;
}
int lengthOfLongestSubstring(char * s){
    int size=strlen(s);
    int max_len=0;
    int *next=malloc(sizeof(int)*256);
    //int next[256]={0};// It is used to record the number of occurrences of each number in each round
    if(size<2)//When the string is empty, it returns 0 directly. When the string has only one character, it returns 1
    {
        return size;
    }
    memset(next,0,sizeof(next));        
    int j=0;
    for(int i=0;i<size;i++)
    {
        j=max(next[s[i]],j);
        max_len=max(max_len,i-j+1);
        next[s[i]]=i+1;   
    }
    return max_len;
};

2.567. Arrangement of strings

Title Description:

Give you two strings s1 and s2, and write a function to judge whether s2 contains the arrangement of s1. If yes, return true; Otherwise, false is returned.

In other words, one of the permutations of s1 is a substring of s2.

Example:

Example 1:
Input: s1 = "ab" s2 = "eidbaooo"
Output: true
 Explanation: s2 contain s1 One of the permutations of ("ba").

Example 2:
Input: s1= "ab" s2 = "eidboaoo"
Output: false

Answer Description:

The key to this question is to understand that s2 contains the arrangement of s1, which means that as long as there is a substring of s2 and the element type and number of s1 are the same. So consider a fixed size of s1 The sliding window of size () is used to solve the problem.

First, use the arrays cnt1 and cnt2 to record the occurrence times of each element in s1 and the occurrence times of elements in s2 current window respectively. If cnt1 and cnt2 are exactly the same, it indicates that they match and return true. Otherwise, move the sliding window back one step as a whole, update cnt2 and continue to judge.

code:

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n1=s1.size();
        int n2=s2.size();
        if(n1>n2)
        {
            return false;
        }
        vector<int> cnt1(26);//It is used to count the occurrence times of s1 characters in the sliding window with a fixed size of n1
        vector<int> cnt2(26);//It is used to count the occurrence times of s2 characters in the sliding window with a fixed size of n1
        for(int i=0;i<n1;i++)
        {
            cnt1[s1[i]-'a']++; 
            cnt2[s2[i]-'a']++;
        }
        if(cnt1==cnt2)
        {
            return true;
        }
        int l=0;
        int r=n1;
        while(r<n2)
        {
            cnt2[s2[l]-'a']--;
            cnt2[s2[r]-'a']++;
            if(cnt1==cnt2)
            {
                return true;
            }
            l++;
            r++;
        }
        return false;
    }
};