Algorithm thought

The idea of the sliding window algorithm is as follows:

  1. We initialize left = right = 0 in string S using the left and right pointer technique in double Pointers, calling the index closed interval [left, right] a “window”.

  2. We enlarge the window [left, right] by increasing the pointer to right until the string in the window meets the requirement (including all characters in T).

  3. At this point, we stop adding right and keep adding left Pointers to shrink the window [left, right] until the string in the window no longer fits the bill (not including all characters in T). Also, each time we add a left, we update the result of a round.

  4. Repeat steps 2 and 3 until right reaches the end of the string S.

int left = 0, right = 0; 
while (right < s.size()) { 
  window.add(s[right]);
  right++; 
  while(valid) { window.remove(s[left]); left++; }}Copy the code

1. Minimum coverage substring

Leetcode-cn.com/problems/mi…

class Solution {
    public String minWindow(String s, String t) {
        //1. Use a map to record how many characters are required, and how many times each character is required
        Map<Character , Integer> need = new HashMap<>();
        for(char c : t.toCharArray()) need.put(c , need.getOrDefault(c , 0) + 1);
        //2. Use a window to indicate whether the condition is met
        Map<Character , Integer> win = new HashMap<>();
        int l = 0 , r = 0 , count = 0;
        int len = Integer.MAX_VALUE , start = 0 , end = 0; // Record the length and start and end positions
        while(r < s.length()){
            char a = s.charAt(r);
            if(need.containsKey(a)){
                win.put(a , win.getOrDefault(a , 0 ) + 1);
                if(win.get(a).intValue() == need.get(a).intValue()) count++;
            }
            r++;
            while(count == need.size()){ // When the condition is met
                if(len > r-l){
                    len = r - l;
                    start = l;
                    end = r;
                }
                char b = s.charAt(l);
                if(need.containsKey(b)){
                    win.put(b , win.getOrDefault(b,0) -1);
                    if(win.get(b) < need.get(b)) count--; } l++; }}returns.substring(start , end); }}Copy the code

2. The oldest string without repeating characters

Leetcode-cn.com/problems/lo…

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        if(n == 0 || n == 1) return n;
        Map<Character , Integer> map = new HashMap<>();
        int res = 0;
        for(int i = 0 , j = 0 ; i < n ; i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                j = Math.max(j , map.get(c));
            }
            map.put(c , i+1);
            res = Math.max(res , i+1 - j);
            
        }
        returnres; }}Copy the code

3. Find all letter heterotopic words in the string

(leetcode-cn.com/problems/fi…).

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        Map<Character,Integer> need = new HashMap<>();
        for(char c : p.toCharArray()) need.put(c , need.getOrDefault(c , 0) + 1);

        Map<Character,Integer> win = new HashMap<>();
        int count = 0 , l = 0 , r = 0;
        while(r < s.length()){
            char a = s.charAt(r);
            if(need.containsKey(a)){
                win.put(a , win.getOrDefault(a , 0) +1);
                if(win.get(a).intValue() == need.get(a).intValue()) count++;
            }

            r++;
            while(count == need.size()){
                if(r - l  == p.length()){ // Add to res if the conditions are met
                    res.add(l);
                }
                char b = s.charAt(l);
                if(need.containsKey(b)){
                    win.put(b , win.getOrDefault(b ,0) -1);
                    if(win.get(b) < need.get(b)) count--; } l++; }}returnres; }}Copy the code

4. Check whether the string contains permutations

Leetcode-cn.com/problems/pe…

class Solution {
    public boolean checkInclusion(String s, String p) {
        Map<Character , Integer> need = new HashMap<>();
        for(char c : s.toCharArray()) need.put(c , need.getOrDefault(c , 0) + 1);

        Map<Character,Integer> win = new HashMap<>();
        int l = 0 , r = 0;
        int count = 0;
        while(r < p.length()){
            char a = p.charAt(r);
            if(need.containsKey(a)){
                win.put(a , win.getOrDefault(a , 0) + 1);
                if(win.get(a).intValue() == need.get(a).intValue()) count++;
            }
            r++;
            while(r - l >= s.length()){
                if(count == need.size()) return true;
                char b = p.charAt(l);
                if(need.containsKey(b)){
                    if(win.get(b) == need.get(b)) count--;
                    win.put(b , win.getOrDefault(b,0) -1); } l++; }}return false; }}Copy the code

Fixed size window problem

1. Maximum sliding window value

Leetcode-cn.com/problems/sl…

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
         if(n < 2) return nums;
        int[] res = new int[n-k+1];
        // The number of array positions in the queue is sorted from largest to smallest
        LinkedList<Integer> list = new LinkedList<>();
        for(int i = 0 ; i < n ; i++){
            //// guarantee from large to small if the front number of small pop-up
            while(! list.isEmpty() && nums[list.peekLast()] <= nums[i]) list.pollLast(); list.addLast(i);// Initialize the window until the window length is k and the next move deletes the expiration value
            if(list.peek() <= i-k) list.poll();
            if(i - k + 1> =0) res[i-k+1] = nums[list.peek()];
        }
        returnres; }}Copy the code

An unfixed size window problem