Given two strings s1
and s2
, return true
if s2
contains a permutation of s1
, or false
otherwise.
In other words, return true
if 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 <= 104
s1
ands2
consist of lowercase English letters.
Companies:
Yandex, Amazon, Oracle, Facebook, Bloomberg
Related Topics:
Hash Table, Two Pointers, String, Sliding Window
Similar Questions:
Store the counts of letters of a
in cnts
array.
- When we consume a letter
b[i]
, we decrement its count. - When we pop a letter
b[i - N]
, we increment its count. We start popping wheni - N >= 0
to make sure the sliding window is at most as long asa
.
Once all the counts in cnts
array are zeros, we return true
. If we reached end of array and still haven't clear out the cnts
, return false
.
The time complexity is O(26 * S2) = O(S2)
.
// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// 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;
}
};
Similar to Solution 1, we keep a sliding window of size a.size()
. Instead of checking the count for 26 characters, we just use a matched
variable to store the number of matched characters within the sliding window.
// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// Time: O(B)
// Space: O(1)
class Solution {
public:
bool checkInclusion(string a, string b) {
if (a.size() > b.size()) return false;
int cnt[26] = {}, matched = a.size(), N = a.size();
for (char c : a) cnt[c - 'a']++;
for (int i = 0; i < b.size(); ++i) {
if (i >= N) matched += cnt[b[i - N] - 'a']++ >= 0;
matched -= cnt[b[i] - 'a']-- > 0;
if (!matched) return true;
}
return false;
}
};
We keep the counts of letters of s1
in goal
array. And we use two pointers i
and j
to consume s2
, and store the counts of letters within range [i, j)
in cnt
array.
- We keep incrementing
j
and the corresponding countcnt[s2[j]]
until it reaches the end orcnt[s2[j]] + 1 <= goal[s2[j]]
. LetX
bes2[j]
thenX
is the letter we don't want to consume. - If the gap between
i
andj
is the length ofs1
, then we've found match and just returntrue
. - Since
s2[j]
is unwanted, we keep poppings2[i]
by incrementingi
untils2[i] == s2[j]
, meanwhile, we decrementcnt[s2[i]]
. - Now
s[i]
ands[j]
are all pointing to the unwanted letterX
, incrementi
andj
both so that thecnt[X]
will be unchanged. Go to Step 1 untilj
reaches end.
// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// Time: O(S2)
// Space: O(1)
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int M = s1.size(), N = s2.size(), i = 0, j = 0, goal[26] = {0}, cnt[26] = {0};
for (char c : s1) goal[c - 'a']++;
for (; j < N; ++i, ++j) {
while (j < N && cnt[s2[j] - 'a'] + 1 <= goal[s2[j] - 'a']) cnt[s2[j++] - 'a']++;
if (j - i == M) return true;
while (j < N && i < j && s2[i] != s2[j]) cnt[s2[i++] - 'a']--;
}
return false;
}
};
Or
// OJ: https://leetcode.com/problems/permutation-in-string/
// Author: github.com/lzl124631x
// Time: O(B)
// Space: O(1)
class Solution {
public:
bool checkInclusion(string a, string b) {
if (a.size() > b.size()) return false;
int cnt[26] = {};
for (char c : a) cnt[c - 'a']++;
for (int i = 0, j = 0; j < b.size(); ++j) {
if (--cnt[b[j] - 'a'] < 0) { // We can't have this `b[j]` in the window
while (b[i] != b[j]) cnt[b[i++] - 'a']++; // keep skipping until `b[i] == b[j]`
cnt[b[i++] - 'a']++; // remove `b[i]` from the window
}
if (j - i + 1 == a.size()) return true; // If the window has the same length as `a`, return true
}
return false;
}
};