# 15. 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
```

## Solution I: (Pattern matching similar to Rabin Karp)

```cpp
class Solution
{
public:
    vector<int> count(string s, int start, int end)
    {
        vector<int> v(26);
        for (int i = start; i <= end; i++)
        {
            v[s[i] - 97]++;
        }
        return v;
    }

    bool compare(vector<int> v1, vector<int> v2)
    {
        for (int i = 0; i < 26; i++)
        {
            if (v1[i] != v2[i])
            {
                return false;
            }
        }
        return true;
    }

    bool checkInclusion(string s1, string s2)
    {

        int n1 = s1.length();
        int n2 = s2.length();

        if (n1 > n2)
        {
            return false;
        }
        vector<int> str1 = count(s1, 0, n1 - 1);

        vector<int> roll = count(s2, 0, n1 - 1);

        for (int i = 0; i <= s2.length() - n1; i++)
        {

            if (compare(str1, roll))
            {
                return true;
            }

            if (i + n1 < n2)
            {
                roll[s2[i] - 97]--;
                roll[s2[i + n1] - 97]++;
            }
        }

        return false;
    }
};
```

**Time Complexity: O(n1 + (n2-n1) \* 26)**

## Solution II: (Optimized )

```cpp
```