Algorithmic Clearance Village – Classic Sliding Window Problem

Table of Contents

Classic sliding window problem

1. The longest substring topic

1.1 The longest substring without repeated characters

1.2 The longest substring containing at most two different characters

1.3 The longest substring containing at most K different characters

2 subarray with minimum length

3 The container that holds the most water

4. Find substring anagrams

4.1 Arrangement of strings

4.2 Find all letters in a string that are in different positions

Classic problem of sliding window

We have already understood the basic idea of sliding windows. Today let us complete the classic algorithm questions about sliding windows.

1. The longest substring topic

This is a high-frequency algorithm question: the longest substring without repeated characters. The specific requirement is that given a string s, please find the length of the longest substring that does not contain repeated characters. For example, if you enter: s =”abcabcbb“, then 3 is output. Because the longest substring without repeated characters is “abc”, so its The length is 3.

If the requirements are changed again, the longest substring containing at most two different characters, or the longest substring containing at most K different characters, what should be done… these All can be solved using sliding windows. And it is essentially a problem-solving template.

1.1 The longest substring without repeating characters

Given a string s, please find the length of the longest substring that does not contain repeated characters. For example:

Input: s="abcabcbb"
Output: 3
Explanation: Because the longest substring without repeated characters is "abc", its length is 3. 

To find the longest substring, you must know the head and tail of the non-duplicate string, and then determine the longest one, so at least two pointers< /strong>, this reminds me of the sliding window idea. Here is a classic idea of using Map. We define a map in the form of K-V. key represents the string currently being accessed, and value is its subscript index value. . Every time we access a new element, we update its subscript to the corresponding index value. The specific process is as follows:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s.length() == 0) return 0;
        //Hash table that stores each letter and its corresponding index
        HashMap<Character, Integer> map = new HashMap<>();
        int left = 0; // Sliding window left pointer
        int max = 0; //Storage the maximum value of a non-duplicate string
        for(int right = 0; right < s.length(); right + + ){
            // If the current character already exists in the map, update the left pointer position of the sliding window
            if(map.containsKey(s.charAt(right))){
                left = Math.max(left, map.get(s.charAt(right)) + 1); // Update left position
            }
            //Update map characters and indexes
            map.put(s.charAt(right), right);
            max = Math.max(max, right - left + 1); // Update the current maximum length of a non-duplicate string
        }
        return max;
    }
}

Input: "eceba"
Output: 3
Explanation: t is "ece", the length is 3

2. Who should be removed when removing, and what is the left after removal: This requires us to design the meaning of Key-Value of a HashMap. Here we put < strong>Characters are used as keys, and the character at the rightmost position of the window is used as the value, because the value we want to remove must be removing the characters on the left side of the window >, that is, the minimum value of the value corresponding to each character in the map (Note: The value here is the value of the character on the rightmost side of the window, so that can completely remove the character ), after removal, left is the removed character corresponding to value + 1,as shown below:

public static int lengthOfLongestSubstringTwoDistinct(String s) {
    if (s.length() < 3) {
        return s.length();
    }
    int left = 0, right = 0;
    // Store the traversed characters and the corresponding rightmost index in the window
    HashMap<Character, Integer> hashmap = new HashMap<>();
    int maxLen = 2; //Storage maximum length
    while (right < s.length()) {
        if (hashmap.size() < 3)
            hashmap.put(s.charAt(right), right + + );
        // If the number of characters reaches 3, delete the leftmost character
        if (hashmap.size() == 3) {
            // Get the leftmost position to be deleted
            int del_idx = Collections.min(hashmap.values());
            hashmap.remove(s.charAt(del_idx));
            //New position of window left
            left = del_idx + 1;
        }
        //Update the length of the longest substring
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

1.3 The longest substring containing at most K different characters

Based on the second question, we will expand the scope of the restriction requirements.

Given a string s, find the longest string T containing at most k different characters. as follows:

Input: s = "eceba", k = 2
Output: 3
Explanation: T is the longest substring "ece" containing at most k = 2 characters, so the length is 3.

This question just replaces 2 with k and lets us specify it ourselves. Is it essentially the same? That’s right, so we just need to change 2 to k. If it exceeds the length 2, it is now k + 1. The specific implementation code is as follows:

public static int lengthOfLongestSubstringKDistinct(String s, int k) {
    if (s.length() < k + 1) {
        return s.length();
    }
    int left = 0, right = 0;
    // Store the traversed characters and the corresponding rightmost index in the window
    HashMap<Character, Integer> hashmap = new HashMap<>();
    int maxLen = k; //Storage maximum length
    while (right < s.length()) {
        if (hashmap.size() < k + 1)
            hashmap.put(s.charAt(right), right + + );
        // If the number of characters reaches 3, delete the leftmost character
        if (hashmap.size() == k + 1) {
            // Get the leftmost position to be deleted
            int del_idx = Collections.min(hashmap.values());
            hashmap.remove(s.charAt(del_idx));
            //New position of window left
            left = del_idx + 1;
        }
        //Update the length of the longest substring
        maxLen = Math.max(maxLen, right - left);
    }
    return maxLen;
}

2 subarray with minimum length

Given an array of n positive integers and a positive integer target. Find the continuous subarray of the minimum length in the array that satisfies the sum ≥ target [numsl,numsl + 1,…, numsr – 1,numsr] and returns its length. If there is no matching subarray, 0 is returned.

Input: target = 7, nums = [2,3,1,2,4,3]
Output: 2
Explanation: Subarray [4,3] is the subarray with the smallest length under this condition. 

This question also involves processing in an interval, so it is still solved using double pointers. It can also be regarded as a queue method.

The basic idea is to first let elements continue to be queued, and when the sum of elements entered into the queue is greater than the target, record the capacity of the queue at this time, and then start Exit the queue until is less than the target and then continue to join the queue.
If is equal to target, record the size of the queue at this time, and then continue to enter the queue first and then leave the queue. Whenever the sum of elements is equal to target, we retain the one with the smallest capacity. The implementation code is as follows:

public static int minSubArrayLen(int target, int[] nums) {
    int left = 0, right = 0, sum = 0, min = Integer.MAX_VALUE;
    while (right < nums. length) {
        //Array elements are continuously added to the queue until they are greater than or equal to target
        sum + = nums[right + + ];
        while (sum >= target) {
            // Update the minimum length at this time
            min = Math.min(min, right - left);
            // Remove the leftmost element, then left + +
            sum -= nums[left + + ];
        }
    }
    return min == Integer.MAX_VALUE ? 0 : min;
}

3 container with the most water

Given an integer array height of length n. There are n vertical lines, and the two endpoints of the i-th line are (i, 0) and (i, height[i]). Find the two lines so that the container formed by them and the x-axis can hold the most water. Returns the maximum amount of water the container can store. As shown below:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The vertical lines in the figure represent the input array [1,8,6,2,5,4,8,3,7]. In this case, the container is capable of holding water
The maximum value is 7 * ( 9 - 2) = 49

This question may seem complicated, but it is actually very simple. When it comes to processing within the interval, let’s assume that the two pointers i, j point to the sink plate height respectively as h[i] , hlj] , in this statethe sink area is S(j). Since the height that can hold water is determined by the shorter one of the two plates, and the length of the base is j – i, the following area formula can be obtained: s(j) = min (h[ i ] ,h[ j ]) x (j – i)

So which plate should we move when looking for the largest area? Let’s analyze it below:

In each state, whether the long board or the short board is narrowed one space toward the middle, it will cause the width of the bottom edge of the sink to be shortened by -1:

? If youmove the short plate inward, the short platemin(h[i] ,h[j]) of the sink may become larger, so thes of the next sink Area may increase
? If you move the long plate inward, the short plate min(h,hli) of the sink will remain unchanged or become smaller, so the area of the next sink must become smaller

Therefore, as long as the dual pointers are initialized, the water tank is divided into left and right ends, and loopmoves the short board inward one space in each round. strong>, and update the maximum area value, until the two pointers meet and jump out; the maximum area can be obtained.

public static int maxArea(int[] height) {
    int i = 0, j = height.length - 1, res = 0;
    while (i < j) {
        //Move the pointer index where the short board is located after each update of the maximum value
        res = height[i] < height[j] ?
                Math.max(res, (j - i) * height[i + + ]) :
                Math.max(res, (j - i) * height[j--]);
    }
    return res;
}

4 Find substring anagrams

Anatomy: If two character strings are only different in the position where the subtitles appear, they are said to be a permutation of each other, or an anagram. Determining whether two strings are arranged is also a basic algorithm for strings.

4.1 Arrangement of Strings

Given two strings s1 and s2, write a function to determine whether s2 contains the arrangement of s1. If so, return true ; otherwise, return false . In other words, one of the permutations of s1 is a substring of s2. Both s1 and s2contain only lowercase letters.

Input: s1 ="ab" s2 ="eidbaooo"
Output: true
Explanation: s2 contains one of the permutations ("ba") of s1

In this question, because the length of the anagram of string s1 must be the same as the length of string s2, there is no need to use expensive sorting.

The so-called allophones are nothing more than two things: letterstypesthe same, and each letter appears The same is true for numbers. The question says that both s1 and s2 are limited to lowercase letters, so we can create an array of size 26, and each position stores the number from a to z. In order For convenience of operation, index we use index=s1.charAt(i) – ‘a’ to represent it. This is a common technique for processing strings At this time, the window’s right moves to the right by executing: charArray2[s2.charAt(right) – ‘a’] + + ; and the left moves to the right< /strong>Just execute int left = right – SLen1; charArray2[s2.charAt(left) – ‘a’]–;

public class CheckInclusion {
    public static boolean checkInclusion(String s1, String s2) {
        int sLen1 = s1.length(), sLen2 = s2.length();
        if (sLen1 > sLen2) {
            return false;
        }
        int[] charArray1 = new int[26]; // Array that stores the number of occurrences of the letter s1
        int[] charArray2 = new int[26]; // Array that stores the number of occurrences of the letter s2
        //Read the first paragraph (the same length as s1) first to judge.
        for (int i = 0; i < sLen1; + + i) {
             + + charArray1[s1.charAt(i) - 'a'];
             + + charArray2[s2.charAt(i) - 'a'];
        }
        // Determine whether the two storage arrays are the same at this time
        if (Arrays.equals(charArray1, charArray2)) {
            return true;
        }
        // The right pointer of s2 continues to traverse to the right and is recorded in the array, removing the data generated by the left pointer.
        for (int right = sLen1; right < sLen2; + + right) {
            //Continue to traverse to the right and record it into the array
            charArray2[s2.charAt(right) - 'a'] + + ;
            int left = right - sLen1; // Left pointer index
            // Decrease the number of occurrences of the left pointer index in the array by one
            charArray2[s2.charAt(left) - 'a']--;
            //Check again whether they are the same
            if (Arrays.equals(charArray1, charArray2)) {
                return true;
            }
        }
        return false;
    }
    // test
    public static void main(String[] args) {
        String s1 = "ab", s2 = "eidbaooo";
        System.out.println(checkInclusion(s1, s2));
    }

}

Input: s="cbaebabacd", p="abc"
Output: [0,6]
explain:
The substring starting at index 0 is "cba", which is an anagram of "abc".
The substring starting at index 6 is "bac", which is an anagram of "abc". 

public class FindAnagrams {
    public static List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }
        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        //First initialize the two arrays separately
        for (int i = 0; i < pLen; i + + ) {
            sCount[s.charAt(i) - 'a'] + + ;
            pCount[p.charAt(i) - 'a'] + + ;
        }
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int left = 0; left < sLen - pLen; left + + ) {
            sCount[s.charAt(left) - 'a']--;
            int right = left + pLen;
            sCount[s.charAt(right) - 'a'] + + ;

            if (Arrays.equals(sCount, pCount)) {
                //The above left is reduced once more, so + 1 is needed
                ans.add(left + 1);
            }
        }
        return ans;
    }
    // test
    public static void main(String[] args) {
        String s = "cbaebabacd", p = "abc";
        System.out.println(findAnagrams(s, p));

    }

}