---

567. Arrangement of strings

Here are two strings s1 and s2 , Write a function to judge s2 Does it include s1 Permutation . If it is , return true ; otherwise , return false .

let me put it another way ,s1 One of the permutations is s2 Of Substring .

Example 1：

Input ：s1 = “ab” s2 = “eidbaooo”
Output ：true
explain ：s2 contain s1 One of the permutations of (“ba”).

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/permutation-in-string
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Their thinking

The sliding window

Balance sheet
Maintain a length of 5 The window of

I owe you two C. Now my window contains a C, Is a valid repayment ,C Must be reduced

An effective repayment

Negative value after subtraction , Not an effective repayment all Immobility

For the first time, the window grows to 5. The window is initially formed
Is this window str2 Permutation
all It's not equal to 0, This window is not str2 Permutation

Still not an effective arrangement
When the window slides
Add a character to the right , If the character exists in the debt table , This character is subtracted from the number in the table
Throw away a character on the left , If this character is in the debt table , This character is added to the number of the table
If the number of a character is reduced to 0, be all–
If a character is added 1, be all++

When all==0 when , Return to the answer

Code

This code returns the starting position of any substring that meets the condition

	public static int containExactly(String s1, String s2) {
    
		if (s1 == null || s2 == null || s1.length() < s2.length()) {
    
			return -1;
		}
		char[] str2 = s2.toCharArray();
		int M = str2.length;
		int[] count = new int[256];
		for (int i = 0; i < M; i++) {
    
			count[str2[i]]++;
		}
		int all = M;
		char[] str1 = s1.toCharArray();
		int R = 0;
		// 0~M-1
		for (; R < M; R++) {
     //  One of the earliest M Characters , Let its window take shape 
			if (count[str1[R]]-- > 0) {
    
				all--;
			}
		}
		//  The window has initially formed , No judgment is valid or invalid , Decide the next position and judge 
		//  The next process , Enter one right in the window , Spit one on the left 
		for (; R < str1.length; R++) {
    
			if (all == 0) {
     // R-1
				return R - M;
			}
			if (count[str1[R]]-- > 0) {
    
				all--;
			}
			if (count[str1[R - M]]++ >= 0) {
    
				all++;
			}
		}
		return all == 0 ? R - M : -1;
	}