## Approach 1: Classic sliding window

• Time:O(|\texttt{s1}| + |\texttt{s2}|)
• Space:O(128) = O(1)

## C++

class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector<int> count(128);
int required = s1.length();

for (const char c : s1)
++count[c];

for (int l = 0, r = 0; r < s2.length(); ++r) {
if (--count[s2[r]] >= 0)
--required;
while (required == 0) {
if (r - l + 1 == s1.length())
return true;
if (++count[s2[l++]] > 0)
++required;
}
}

return false;
}
};

## JAVA

class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] count = new int[128];
int required = s1.length();

for (final char c : s1.toCharArray())
++count[c];

for (int l = 0, r = 0; r < s2.length(); ++r) {
if (--count[s2.charAt(r)] >= 0)
--required;
while (required == 0) {
if (r - l + 1 == s1.length())
return true;
if (++count[s2.charAt(l++)] > 0)
++required;
}
}

return false;
}
}

## Approach 2: Constant-sized moving window

• Time:O(|\texttt{s1}| + |\texttt{s2}|)
• Space:O(128) = O(1)

## C++

class Solution {
public:
bool checkInclusion(string s1, string s2) {
vector<int> count(128);
int required = s1.length();

for (const char c : s1)
++count[c];

for (int r = 0; r < s2.length(); ++r) {
if (--count[s2[r]] >= 0)
--required;
if (r >= s1.length())  // the window is oversized
if (++count[s2[r - s1.length()]] > 0)
++required;
if (required == 0)
return true;
}

return false;
}
};

## JAVA

class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] count = new int[128];
int required = s1.length();

for (final char c : s1.toCharArray())
++count[c];

for (int r = 0; r < s2.length(); ++r) {
if (--count[s2.charAt(r)] >= 0)
--required;
if (r >= s1.length()) // the window is oversized
if (++count[s2.charAt(r - s1.length())] > 0)
++required;
if (required == 0)
return true;
}

return false;
}
}

## Python

class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
count = Counter(s1)
required = len(s1)

for r, c in enumerate(s2):
count[c] -= 1
if count[c] >= 0:
required -= 1
if r >= len(s1):
count[s2[r - len(s1)]] += 1
if count[s2[r - len(s1)]] > 0:
required += 1
if required == 0:
return True

return False