~/leetcode $ 567. Permutation-In-String

This question doesn’t seem too bad. First, get the character frequencies for all characters in s1 and then use a sliding window approach to see if the character frequency of any window matches the character frequency of s1.

Few things to keep in mind:

• we can reset our window completely everytime we hit an invalid character (character not within our window)
• we need to update our left pointer if we overflow the character frequency for an existing character

We loop until the end of the s2 string, terminating early if we see a match.

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char, int> s1freq {};
        unordered_map<char, int> s2freq {};

        // preprocess s1
        for (char c: s1) {
            ++s1freq[c];
        }

        // sliding window
        int left = 0;
        for (int right = 0; right < s2.length(); ++right) {
            ++s2freq[s2[right]];
            // if we come across valid but overflow
            while (s1freq.contains(s2[right]) && s2freq[s2[right]] > s1freq[s2[right]]) {
                cout << "overflow\n";
                --s2freq[s2[left++]];
            }
            // if we come across invalid
            if (!s1freq.contains(s2[right])) {
                cout << "invalid\n";
                left = right + 1;
                s2freq = {};
            }

            if (s1freq == s2freq) {
                return true;
            }
        }

        return false;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Time Taken: 9m 19s