directory

• Summary and code framework
• 76. Minimum coverage substring
• • The sliding window
  • Code and comments
• 567. Permutation of strings
• • The sliding window
• 438. Find all letter heterotopic words in the string
• 3. The oldest string without repeating characters
• • In the framework
• reference

Summary and code framework

The sliding window technique is a two-pointer technique. The idea is to maintain a window, keep sliding, and then update the answer. The general framework is as follows: [Refer to the algorithm cheat sheet of Labuladong]

int left = 0, right = 0;

while(right < s.size())
{
	// Enlarge the window
	window.add(s[right]);
	right++;
	
	while(window needs shrink)
	{
		// Zoom out
		window.remove(s[left]); left++; }}Copy the code

Main details: 1, how to add new elements to the window 2, how to shrink the window 3, in which stage of the window sliding update results

// Sliding window algorithm framework
void slidingWindow(string s, string t)
{
	unordered_map<char.int> need, window;
	for(char c : t) need[c]++;
	int left = 0, right = 0;
	int valid = 0;
	while(right < s.size())
	{
		//c is the element to be moved into the window
		char c  = s[right];
		// Move the window right
		right++;
		// Update data in window (right move window)
		
		/ * * * * * * * * * * * * * * * * * * * /
		/**debug output position ***/
		cout << "window:[ "<<left << "," << right <<"]"<<endl;
		/ * * * * * * * * * * * * * * * * * * /
		// Determine whether the left window needs to be shrunk
		while(window needs shrink)
		{
			//d is the character to move out of the window
			char d = s[left];
			// Move the window left
			left++;
			// Perform a series of updates to the data in the window (move the window left)}}}Copy the code

76. Minimum coverage substring

The sliding window

1, initialize the window and need hash tables, record the characters in the window and the characters to be completed:

unordered_map<char.int> need,window;
for(char c : t) need[c]++;
Copy the code

2. Use left and right variables to initialize both ends of the window. The interval is left closed and right open.

int left = 0, right = 0;
while(right < s.size())
{
	// Start sliding
}
Copy the code

Valid_length == need.size() specifies the number of characters in the window that meet the need condition. If valid_length == need.size(), the window meets the need condition.

int valid_length;
Copy the code

When right expands to the right, it checks the new element. If it is an element in need, the element in window is +1. Then it checks whether the number of elements in window is the same as the number of elements in need. Valid_length = 1; if “right” is moved and “window” is expanded, which data should be updated?

Update window counter

2. What data should be updated when left moves to shrink window?

Update window counter

3. Under what condition do you pause expanding window and start moving left to shrink Window?

When the valid length is equal to the need size, the window should be shrunk

4. Should the result be performed when the window is enlarged or shrunk?

Update results when the window shrinks

Code and comments

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char.int> window,need;
        // Record what elements are in t and the number of each element
        for(char c : t) need[c]++;
        // Initialize window boundaries
        int right = 0, left = 0;
        //window Specifies the number of elements that satisfy the need condition
        int valid_length = 0;
        // Results in the starting address and length of the string in s, so that the entire string is not updated each time
        int start = 0 , length = INT_MAX;
        while(right < s.size())
        {
            //****************** Expansion window **************
            // Expand the window
            right++;
            // Add new elements
            char c = s[right - 1]; 
            // Determine if the element is in need
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c]) 
                    valid_length++;
            }
            //******************* Zoom out *************
            // If all elements in need are inside the window and each element has the same frequency as the elements inside the window, then an answer is obtained, the answer is recorded, and the window is narrowed to get a better answer
            while(valid_length == need.size())
            {
                // If this answer is shorter than the last one, we will update the answer
                if(right - left < length)
                {
                    start = left;
                    length = right - left;
                }
                // The left boundary moves to the left
                left++;
                //d is the element just removed from the window
                char d = s[left - 1];
                // if d appears in need
                if(need.count(d))
                {
                    // If the d element appears at window and need at the same frequency before
                    if(window[d] == need[d])
                    {
                        // The frequency is not the same, so this element is not satisfied.valid_length--; } window[d]--; }}}// If length is not updated, s does not contain characters in t or does not meet the frequency of characters, return an empty string, otherwise, use substr to return the substring
        return length == INT_MAX ? "" : s.substr(start,length); }};Copy the code

567. Permutation of strings

Leetcode-cn.com/problems/pe… Given two strings s1 and s2, write a function to determine whether S2 contains permutations of s1.

In other words, one of the permutations of the first string is a substring of the second string.

Example 1:

Input: s1 = “ab” s2 = “eidbaooo” Output: True Explanation: S2 contains one of the permutations of s1 (” ba “).

Example 2:

Input: s1= ab s2 = eidBOAOo Output: False

Note:

The entered string contains only lowercase letters. Both strings are between [1, 10,000] in length

The sliding window

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char.int> window,need;
        for(char c : s1) need[c]++;
        int left = 0,right = 0;
        int valid_length = 0;
        while(right < s2.size())
        {
            / / expansion of the window
            right++;
            char c = s2[right - 1];
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c]) valid_length++;
            }
            / / narrow window
            while(right - left >= s1.size())
            {
                if(valid_length == need.size()) return true;
                left++;
                char d = s2[left - 1];
                if(need.count(d))
                {
                    if(window[d] == need[d]) valid_length--; window[d]--; }}}return false; }};Copy the code

438. Find all letter heterotopic words in the string

Leetcode-cn.com/problems/fi… Given a string s and a non-empty string p, find all substrings of the alphabetic alloword p in S and return the starting index of these substrings.

The string contains only lowercase letters, and the length of the string s and p cannot exceed 20100.

Note: An anagram word is a string with the same letters but different arrangements. Regardless of the order in which the answers are printed. Example 1:

Input: s: “cbaebabacd” p: “ABC” Output: [0, 6] Explanation: The substring with the starting index equal to 0 is “CBA”, which is an anagram of “ABC”. The substring whose starting index equals 6 is “bac”, which is an anagram of “ABC”.

Example 2: * * * *

Input: s: “abab” p: “ab” Output: [0, 1, 2] Explanation: The substring whose starting index equals 0 is “ab”, which is an alphabetic allograph of “ab”. The substring with an index equal to 1 is “ba”, which is an anagram of “ab”. The substring whose starting index equals 2 is “ab”, which is an alphabetic allotopic of “ab”.

Direct set

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if(s.empty()) return {};
        vector<int> result;
        unordered_map<char.int> need,window;
        for(char c : p) need[c]++;
        int left = 0,right = 0;
        int valid_length = 0;
        while(right < s.size())
        {
            //expand window
            right++;
            char c = s[right - 1];
            if(need.count(c))
            {
                window[c]++;
                if(window[c] == need[c]) { valid_length++; }}//shrink window
            while(right - left >= p.size())
            {
                if(valid_length == need.size())
                {
                    result.emplace_back(left);
                }
                left++;
                char d = s[left - 1];
                if(need.count(d))
                {
                    if(window[d] == need[d]) { valid_length--; } window[d]--; }}}returnresult; }};Copy the code

3. The oldest string without repeating characters

In the framework

Remove need and Valid, and update window data only by updating the window counter. If window[c] is greater than 1, it indicates that there are repeated characters in the window. Update results: Update results are placed after the shrink window because there are no repeat characters after the shrink window.

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        int res = 0;
        unordered_map<char.int> window;
        int left = 0, right = 0;
        while(right < s.size())
        {
            //expand window
            right++;
            char c = s[right - 1];
            window[c]++;
            // If a new element enters the window with a duplicate element within the window, the left needs to be moved
            //shrink window
            while(window[c] > 1)
            {
                left++;
                window[s[left - 1]]--;
            }
            res = max(res,right - left);
        }
        returnres; }};Copy the code

reference