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)

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 )