567. Permutation in String

sliding window O(n) time O(1) space
维护定长sliding window和一个cnt，cnt表示当前sliding window内符合要求的字符的个数，只有当cnt为m即sliding window的长度时，说明所有字符都是符合要求的，则找到了一个permutation

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = size(s1), n = size(s2);
        if (m > n) return false;
        int f[26] = {0};
        for (char c : s1) {
            ++f[c - 'a'];
        }
        for (int cnt = 0, i = 0; i < n; ++i) {
            if (--f[s2[i] - 'a'] >= 0) {
                ++cnt;
            }
            if (i >= m && ++f[s2[i - m] - 'a'] > 0) {
                --cnt;
            }
            if (cnt == m) return true;
        }
        return false;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m = size(s1), n = size(s2);
        if (m > n) return false;
        int f[26] = {0};
        for (char c : s1) {
            ++f[c - 'a'];
        }
        for (int cnt = m, i = 0; i < n; ++i) {
            if (--f[s2[i] - 'a'] >= 0) {
                --cnt;
            }
            if (i >= m && ++f[s2[i - m] - 'a'] > 0) {
                ++cnt;
            }
            if (cnt == 0) return true;
        }
        return false;
    }
};

朴素解法即可，维护两个map，每次移动窗口得到一个新map检查是不是一样
跟438. Find All Anagrams in a String几乎一样

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> m1(26);
        for (char c : s1) {
            ++m1[c - 'a'];
        }
        vector<int> m2(26);
        int m = s1.length(), n = s2.length();
        for (int i = 0; i < n; ++i) {
            ++m2[s2[i] - 'a'];
            if (i >= m - 1) {
                if (m1 == m2) return true;
                --m2[s2[i - m + 1] - 'a'];
            }
        }
        return false;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> m1(26);
        for (char c : s1) {
            ++m1[c - 'a'];
        }
        vector<int> m2(26);
        int m = s1.length(), n = s2.length();
        for (int i = 0; i < n; ++i) {
            if (i >= m) {
                --m2[s2[i - m] - 'a'];
            }
            ++m2[s2[i] - 'a'];
            if (m1 == m2) return true;
        }
        return false;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int m1[26] = {0}, m2[26] = {0};
        for (auto c : s1) {
            ++m1[c - 'a'];
        }
        s2 += "a"; // padding简化代码
        int n1 = s1.length(), n2 = s2.length();
        if (n1 > n2) return false;
        for (int i = 0; i < n2; ++i) {
            if (i >= n1) {
                if (isSame(m1, m2)) return true;
                --m2[s2[i - n1] - 'a'];
            }
            ++m2[s2[i] - 'a'];
        }
        return false;
    }

    bool isSame(int lhs[], int rhs[]) {
        for (int i = 0; i < 26; ++i) {
            if (lhs[i] != rhs[i]) return false;
        }
        return true;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        vector<int> m1(26);
        for (char c : s1) {
            ++m1[c - 'a'];
        }
        int m = s1.length(), n = s2.length();
        vector<int> m2(26);
        s2 += "a";
        for (int i = 0; i <= n; ++i) {
            if (i >= m) {
                if (m1 == m2) return true;
                --m2[s2[i - m] - 'a'];
            }
            ++m2[s2[i] - 'a'];
        }
        return false;
    }
};