> For the complete documentation index, see [llms.txt](https://abhyas-kanaujia.gitbook.io/lb-dsa-notes-and-homework-abhyas/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://abhyas-kanaujia.gitbook.io/lb-dsa-notes-and-homework-abhyas/14-character-array-and-strings/discord-homework/10.-permutation-in-string.md).

# 10. Permutation in String

<mark style="color:green;">3rd Solution is 93% faster than all submissions</mark>

## Generate all permutations and see if it is present

```cpp
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!)$$ <mark style="color:red;">TLE</mark>

## Count number of chars in each window using map

```cpp
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)$$ <mark style="color:red;">TLE</mark>

## Count number of chars in each window using lookup table

Lesson: Map is slower than lookup table

```cpp
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: <mark style="color:green;">Accepted</mark>

$$
O(n)
$$

Space Complexity:&#x20;

$$
O(n)
$$