<p>Given two strings <code>s1</code> and <code>s2</code>, return <code>true</code><em> if </em><code>s2</code><em> contains a permutation of </em><code>s1</code><em>, or </em><code>false</code><em> otherwise</em>.</p>

<p>In other words, return <code>true</code> if one of <code>s1</code>&#39;s permutations is the substring of <code>s2</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;ab&quot;, s2 = &quot;eidbaooo&quot;
<strong>Output:</strong> true
<strong>Explanation:</strong> s2 contains one permutation of s1 (&quot;ba&quot;).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s1 = &quot;ab&quot;, s2 = &quot;eidboaoo&quot;
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s1.length, s2.length &lt;= 10<sup>4</sup></code></li>
	<li><code>s1</code> and <code>s2</code> consist of lowercase English letters.</li>
</ul>

class Solution {
public:
    // We can consider every possible substring in the long string s2 of the same length as that of s1 and check the frequency of occurence of the characters appearing in the two.
    //Time complexity : O(m + 26m(n-m))
    //Space complexity : O(1)
    bool checkInclusion(const string& s1, const string& s2) {
        int m = s1.size(), n = s2.size();
        if (m > n) return false;

        unordered_map<char, int> s1map;
        for (char c : s1) {
            s1map[c]++;
        }

        for (int i = 0; i <= n - m; ++i) {
            unordered_map<char, int> s2map;
            for (int j = 0; j < m; ++j) {
                s2map[s2[i + j]]++;
            }
            if (matches(s1map, s2map)) return true;
        }
        return false;
    }

private:
    bool matches(const unordered_map<char, int>& s1map, const unordered_map<char, int>& s2map) {
        for (const auto& [key, count] : s1map) {
            auto it = s2map.find(key);
            if (it == s2map.end() || it->second != count) {
                return false;
            }
        }
        return true;
    }
};

83659