567. Permutation in String

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input: s1 = "ab" s2 = "eidbaooo"
Output: True
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"
Output: False

Note:

1. The input strings only contain lower case letters.

2. The length of both given strings is in range [1, 10,000].

// Sliding window
bool checkInclusion(string s1, string s2) { // time: O(len1 + len2); space: O(1)
    int len1 = s1.length(), len2 = s2.length();
    vector<int> record(128, 0);
    for (const char& ch : s1) ++record[ch];
    int begin = 0, end = 0, counter = len1;
    while (end < len2) {
        if (record[s2[end++]]-- >= 1) --counter;
        if (counter == 0) return true;
        if (end - begin == len1 && record[s2[begin++]]++ >= 0) ++counter;
    }
    return false;
}