10. Permutation in String

3rd Solution is 93% faster than all submissions

Generate all permutations and see if it is present

bool res = false;
bool checkInclusion(string s1, string s2) {
    permute(s1, s2, 0);
    return res;
}
void permute(string s1, string s2, int i) {
    if(i >= s1.length()) {
        if(s2.find(s1) != string::npos)
            res = true;
    } else {
        for(int j = i; j < s1.length(); j++) {
            swap(s1[i], s1[j]);
            permute(s1, s2, i + 1);
            swap(s1[i], s1[j]);
        }
    }

}

Time Complexity: $$O(n!)$$ TLE

Count number of chars in each window using map

bool checkInclusion(string s1, string s2) {
    if(s1.length() > s2.length()) 
        return false;

    map<char, int> s1Freq;

    for(char ch: s1)
        s1Freq[ch]++;

    for(int i = 0; i <= s2.length() - s1.length(); i++) {
        map<char, int> s2Freq;
        for(int j = 0; j < s1.length(); j++) 
            s2Freq[s2[i + j]]++;
        if(s2Freq == s1Freq)
            return true;
    }
    return false;
}

Time Complexity: $$O(n^2)$$ TLE

Count number of chars in each window using lookup table

Lesson: Map is slower than lookup table

inline bool check(const vector<int> &freq) {
    for(int x: freq)
       if(x < 0 || x > 0) 
           return false;
    return true;
}

bool checkInclusion(string part, string str) {        
    // part not longer than str
    if(str.size() < part.size())
        return false;

    // loopup table
    vector<int> freq(26, 0);

    // count increment for chars in part
    for(char ch: part)
        freq[ch - 'a']++;

    // count decrement for chars in first window
    for(int i = 0; i < part.size(); i++)
        freq[str[i] - 'a']--;

    // check if all 0 entries in freq
    if(check(freq))
            return true;

    for(int i = part.size(); i < str.size(); i++) {
        // count increment for removed char from window
        freq[str[i - part.size()] - 'a']++;
        // count decrement for added char in window
        freq[str[i] - 'a']--;

    // check if all 0 entries in freq            
        if(check(freq))
            return true;
    }

    return false;
}

Time Complexity: Accepted

$$O(n)$$

Space Complexity:

$$O(n)$$