# 567. 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
``````

Note:

1. The input strings only contain lower case letters.
2. The length of both given strings is in range [1, 10,000].

``````class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size();
vector<int> m1(128), m2(128);
for (int i = 0; i < n1; ++i) {
++m1[s1[i]]; ++m2[s2[i]];
}
if (m1 == m2) return true;
for (int i = n1; i < n2; ++i) {
++m2[s2[i]];
--m2[s2[i - n1]];
if (m1 == m2) return true;
}
return false;
}
};
``````

``````class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size(), left = 0;
vector<int> m(128);
for (char c : s1) ++m[c];
for (int right = 0; right < n2; ++right) {
if (--m[s2[right]] < 0) {
while (++m[s2[left++]] != 0) {}
} else if (right - left + 1 == n1) return true;
}
return n1 == 0;
}
};
``````

``````class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n1 = s1.size(), n2 = s2.size(), cnt = n1, left = 0;
vector<int> m(128);
for (char c : s1) ++m[c];
for (int right = 0; right < n2; ++right) {
if (m[s2[right]]-- > 0) --cnt;
while (cnt == 0) {
if (right - left + 1 == n1) return true;
if (++m[s2[left++]] > 0) ++cnt;
}
}
return false;
}
};
``````

Minimum Window Substring

https://discuss.leetcode.com/topic/87856/sliding-window-o-n-c

https://discuss.leetcode.com/topic/87845/java-solution-sliding-window

https://discuss.leetcode.com/topic/87861/c-java-clean-code-with-explanation

https://discuss.leetcode.com/topic/87884/8-lines-slide-window-solution-in-java

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation