##### Welcome to Subscribe On Youtube
• import java.util.Arrays;

/*
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
Note:
The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

*/

public class Permutation_in_String {

public static void main(String[] args) {
Permutation_in_String out = new Permutation_in_String();
Solution s = out.new Solution();

System.out.println(s.checkInclusion("ab", "eidbaooo"));
System.out.println(s.checkInclusion("ab", "eidboaoo"));
}

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

int window = s1.length();

// N * N
for(int i = 0; i + window - 1 < s2.length(); i++) {
if (isPerm(s1, s2.substring(i, i + window))) {
return true;
}
}

return false;
}

// better permutation check: o(N)
public boolean isPerm(String s1, String s2) {

if(s1.length() != s2.length()) {
return false;
}

int[] count = new int[256];

// each char of s1: +1
// each char of s2: -1
// final check: permutation if all 0s array
for(int i = 0; i < s1.length(); i++) {
char s1char = s1.charAt(i);
count[s1char] = count[s1char] + 1;

char s2char = s2.charAt(i);
count[s2char] = count[s2char] - 1;
}

for(int each: count) {
if (each != 0) {
return false;
}
}

return true;
}
}

// Time Limit Exceeded
public class Solution2 {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}

int window = s1.length();

// N * NlogN
for(int i = 0; i + window - 1 < s2.length(); i++) {
if (isPerm(s1, s2.substring(i, i + window))) {
return true;
}
}

return false;
}

// NlogN
public boolean isPerm(String s1, String s2) {

if(s1.length() != s2.length()) {
return false;
}

char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();

Arrays.sort(c1); // NlogN
Arrays.sort(c2);

for(int i = 0; i < c1.length; i++) {
if(c1[i] != c2[i]) {
return false;
}
}
return true;
}
}
}

• // OJ: https://leetcode.com/problems/permutation-in-string/
// Time: O(B)
// Space: O(1)
class Solution {
public:
bool checkInclusion(string a, string b) {
if (a.size() > b.size()) return false;
int N = a.size(), cnts[26] = {};
for (char c : a) cnts[c - 'a']++;
for (int i = 0; i < b.size(); ++i) {
cnts[b[i] - 'a']--;
if (i - N >= 0) cnts[b[i - N] - 'a']++;
bool match = true;
for (int j = 0; j < 26 && match; ++j) {
if (cnts[j]) match = false;
}
if (match) return true;
}
return false;
}
};

• class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
need, window = {}, {}
validate, left, right = 0, 0, 0
for c in s1:
window[c] = 0
if c in need:
need[c] += 1
else:
need[c] = 1
# sliding window
for right in range(len(s2)):
c = s2[right]
if c in need:
window[c] += 1
if window[c] == need[c]:
validate += 1
while right - left + 1 >= len(s1):
if validate == len(need):
return True
d = s2[left]
left += 1
if d in need:
if window[d] == need[d]:
validate -= 1
window[d] -= 1
return False

############

class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
d = {}
n = len(s1)
for c in s1:
d[c] = d.get(c, 0) + 1
window = {}
for i, c in enumerate(s2):
window[c] = window.get(c, 0) + 1
if i >= len(s1):
window[s2[i - n]] = window.get(s2[i - n], 0) - 1
if window[s2[i - n]] == 0:
del window[s2[i - n]]
if window == d:
return True
return False

• func checkInclusion(s1 string, s2 string) bool {
need, window := make(map[byte]int), make(map[byte]int)
validate, left, right := 0, 0, 0
for i := range s1 {
need[s1[i]] += 1
}
for ; right < len(s2); right++ {
c := s2[right]
window[c] += 1
if need[c] == window[c] {
validate++
}
// shrink window
for right-left+1 >= len(s1) {
if validate == len(need) {
return true
}
d := s2[left]
if need[d] == window[d] {
validate--
}
window[d] -= 1
left++
}
}
return false
}

• function checkInclusion(s1: string, s2: string): boolean {
// 滑动窗口方案
if (s1.length > s2.length) {
return false;
}

const n = s1.length;
const m = s2.length;

const toCode = (s: string) => s.charCodeAt(0) - 97;
const isMatch = () => {
for (let i = 0; i < 26; i++) {
if (arr1[i] !== arr2[i]) {
return false;
}
}
return true;
};

const arr1 = new Array(26).fill(0);
for (const s of s1) {
const index = toCode(s);
arr1[index]++;
}

const arr2 = new Array(26).fill(0);
for (let i = 0; i < n; i++) {
const index = toCode(s2[i]);
arr2[index]++;
}

for (let l = 0, r = n; r < m; l++, r++) {
if (isMatch()) {
return true;
}

const i = toCode(s2[l]);
const j = toCode(s2[r]);
arr2[i]--;
arr2[j]++;
}
return isMatch();
}

• use std::collections::HashMap;

impl Solution {
// 测试两个哈希表是否匹配
fn is_match(m1: &HashMap<char, i32>, m2: &HashMap<char, i32>) -> bool {
for (k, v) in m1.iter() {
if m2.get(k).unwrap_or(&0) != v {
return false;
}
}
true
}
pub fn check_inclusion(s1: String, s2: String) -> bool {
if s1.len() > s2.len() {
return false;
}
let mut m1 = HashMap::new();
let mut m2 = HashMap::new();
// 初始化表 1
for c in s1.chars() {
m1.insert(c, m1.get(&c).unwrap_or(&0) + 1);
}
let cs: Vec<char> = s2.chars().collect();
// 初始化窗口
let mut i = 0;
while i < s1.len() {
m2.insert(cs[i], m2.get(&cs[i]).unwrap_or(&0) + 1);
i += 1;
}
if Self::is_match(&m1, &m2) {
return true;
}
// 持续滑动窗口，直到匹配或超出边界
let mut j = 0;
while i < cs.len() {
m2.insert(cs[j], m2.get(&cs[j]).unwrap_or(&1) - 1);
m2.insert(cs[i], m2.get(&cs[i]).unwrap_or(&0) + 1);
j += 1;
i += 1;
if Self::is_match(&m1, &m2) {
return true;
}
}
false
}
}

• class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() > s2.length())
return false;
if (s2.indexOf(s1) >= 0)
return true;
int[] counts1 = new int[26];
int[] counts2 = new int[26];
int length1 = s1.length(), length2 = s2.length();
for (int i = 0; i < length1; i++) {
char c1 = s1.charAt(i);
counts1[c1 - 'a']++;
char c2 = s2.charAt(i);
counts2[c2 - 'a']++;
}
if (checkSubstring(counts1, counts2))
return true;
for (int i = length1; i < length2; i++) {
char prevC = s2.charAt(i - length1), curC = s2.charAt(i);
counts2[prevC - 'a']--;
counts2[curC - 'a']++;
if (checkSubstring(counts1, counts2))
return true;
}
return false;
}

public boolean checkSubstring(int[] counts1, int[] counts2) {
for (int i = 0; i < 26; i++) {
if (counts1[i] != counts2[i])
return false;
}
return true;
}
}

• // OJ: https://leetcode.com/problems/permutation-in-string/
// Time: O(B)
// Space: O(1)
class Solution {
public:
bool checkInclusion(string a, string b) {
if (a.size() > b.size()) return false;
int N = a.size(), cnts[26] = {};
for (char c : a) cnts[c - 'a']++;
for (int i = 0; i < b.size(); ++i) {
cnts[b[i] - 'a']--;
if (i - N >= 0) cnts[b[i - N] - 'a']++;
bool match = true;
for (int j = 0; j < 26 && match; ++j) {
if (cnts[j]) match = false;
}
if (match) return true;
}
return false;
}
};

• class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
need, window = {}, {}
validate, left, right = 0, 0, 0
for c in s1:
window[c] = 0
if c in need:
need[c] += 1
else:
need[c] = 1
# sliding window
for right in range(len(s2)):
c = s2[right]
if c in need:
window[c] += 1
if window[c] == need[c]:
validate += 1
while right - left + 1 >= len(s1):
if validate == len(need):
return True
d = s2[left]
left += 1
if d in need:
if window[d] == need[d]:
validate -= 1
window[d] -= 1
return False

############

class Solution(object):
def checkInclusion(self, s1, s2):
"""
:type s1: str
:type s2: str
:rtype: bool
"""
d = {}
n = len(s1)
for c in s1:
d[c] = d.get(c, 0) + 1
window = {}
for i, c in enumerate(s2):
window[c] = window.get(c, 0) + 1
if i >= len(s1):
window[s2[i - n]] = window.get(s2[i - n], 0) - 1
if window[s2[i - n]] == 0:
del window[s2[i - n]]
if window == d:
return True
return False

• func checkInclusion(s1 string, s2 string) bool {
need, window := make(map[byte]int), make(map[byte]int)
validate, left, right := 0, 0, 0
for i := range s1 {
need[s1[i]] += 1
}
for ; right < len(s2); right++ {
c := s2[right]
window[c] += 1
if need[c] == window[c] {
validate++
}
// shrink window
for right-left+1 >= len(s1) {
if validate == len(need) {
return true
}
d := s2[left]
if need[d] == window[d] {
validate--
}
window[d] -= 1
left++
}
}
return false
}

• function checkInclusion(s1: string, s2: string): boolean {
// 滑动窗口方案
if (s1.length > s2.length) {
return false;
}

const n = s1.length;
const m = s2.length;

const toCode = (s: string) => s.charCodeAt(0) - 97;
const isMatch = () => {
for (let i = 0; i < 26; i++) {
if (arr1[i] !== arr2[i]) {
return false;
}
}
return true;
};

const arr1 = new Array(26).fill(0);
for (const s of s1) {
const index = toCode(s);
arr1[index]++;
}

const arr2 = new Array(26).fill(0);
for (let i = 0; i < n; i++) {
const index = toCode(s2[i]);
arr2[index]++;
}

for (let l = 0, r = n; r < m; l++, r++) {
if (isMatch()) {
return true;
}

const i = toCode(s2[l]);
const j = toCode(s2[r]);
arr2[i]--;
arr2[j]++;
}
return isMatch();
}

• use std::collections::HashMap;

impl Solution {
// 测试两个哈希表是否匹配
fn is_match(m1: &HashMap<char, i32>, m2: &HashMap<char, i32>) -> bool {
for (k, v) in m1.iter() {
if m2.get(k).unwrap_or(&0) != v {
return false;
}
}
true
}
pub fn check_inclusion(s1: String, s2: String) -> bool {
if s1.len() > s2.len() {
return false;
}
let mut m1 = HashMap::new();
let mut m2 = HashMap::new();
// 初始化表 1
for c in s1.chars() {
m1.insert(c, m1.get(&c).unwrap_or(&0) + 1);
}
let cs: Vec<char> = s2.chars().collect();
// 初始化窗口
let mut i = 0;
while i < s1.len() {
m2.insert(cs[i], m2.get(&cs[i]).unwrap_or(&0) + 1);
i += 1;
}
if Self::is_match(&m1, &m2) {
return true;
}
// 持续滑动窗口，直到匹配或超出边界
let mut j = 0;
while i < cs.len() {
m2.insert(cs[j], m2.get(&cs[j]).unwrap_or(&1) - 1);
m2.insert(cs[i], m2.get(&cs[i]).unwrap_or(&0) + 1);
j += 1;
i += 1;
if Self::is_match(&m1, &m2) {
return true;
}
}
false
}
}