• ㊗️
• 大家
• offer
• 多多！

## Problem

Given two strings s1 and s2, return true if s2 contains the permutation of s1.

In other words, one of s1’s permutations is the substring of s2.

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


Constraints:

• $1 <= s1.length, s2.length <= 10^4$
• s1 and s2 consist of lowercase English letters.

## Code

438. Find All Anagrams in a String

class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;

int[] dict1 = new int[26];
int[] dict2 = new int[26];

for (int i = 0; i < s1.length(); i++) {
dict1[s1.charAt(i) - 'a']++;
dict2[s2.charAt(i) - 'a']++;
}

if (helper(dict1, dict2)) return true;

for (int i = 1; i <= s2.length() - s1.length(); i++) {
dict2[s2.charAt(i - 1) - 'a']--;
dict2[s2.charAt(i + s1.length() - 1) - 'a']++;

if (helper(dict1, dict2)) return true;
}

return false;
}

public boolean helper(int[] dict1, int[] dict2) {
for (int i = 0; i < 26; i++) {
if (dict1[i] != dict2[i]) return false;
}

return true;
}
}

class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) return false;

int[] dict1 = new int[26];
int[] dict2 = new int[26];

for (int i = 0; i < s1.length(); i++) {
dict1[s1.charAt(i) - 'a']++;
dict2[s2.charAt(i) - 'a']++;
}

int count = 0;

for (int i = 0; i < 26; i++) {
if (dict1[i] == dict2[i])
count++;
}

if(count == 26) return true;

for (int i = 1; i <= s2.length() - s1.length(); i++) {
int left = s2.charAt(i - 1) - 'a';
int right = s2.charAt(i + s1.length() - 1) - 'a';

dict2[right]++;

if (dict2[right] == dict1[right]) {
count++;
} else if (dict2[right] == dict1[right] + 1) {
count--;
}

dict2[left]--;

if (dict2[left] == dict1[left]) {
count++;
} else if (dict2[left] == dict1[left] - 1) {
count--;
}

if (count == 26) return true;
}

return false;
}
}