567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

滑动窗口

欠账表
维持一个长度为5的窗口

欠你两个C。现在我窗口含了一个C，是一个有效还款,C须减减

一次有效的还款

减减后负值,不是一次有效的还款all不动

窗口第一次成长到5.窗口初步形成
这个窗口是不是str2的排列
all不等于0,这个窗口不是str2的排列

依然不是有效的排列
窗口滑动的时候
右边加入一个字符,如果该字符存在在欠债表里,该字符在表的数减减
左边扔掉一个字符,如果该字符是在欠债表里的,该字符在表的数加加
如果一个字符数被减为0,则all--
如果一个字符被加到1,则all++

当all==0时,返回答案

代码

这个代码为返回任意满足条件的一个子串的起始位置

    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++) { // 最早的M个字符，让其窗口初步形成
            if (count[str1[R]]-- > 0) {
                all--;
            }
        }
        // 窗口初步形成了，并没有判断有效无效，决定下一个位置一上来判断
        // 接下来的过程，窗口右进一个，左吐一个
        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;
    }