# 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)
$$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://abhyas-kanaujia.gitbook.io/lb-dsa-notes-and-homework-abhyas/14-character-array-and-strings/discord-homework/10.-permutation-in-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.