Description
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-
s1ands2consist of lowercase English letters.
Solutions
Solution 1
Intuition
Code
class Solution {
public:
unordered_map<char, int> map1, map2;
bool check(char& c) {
if (map1.count(c) && map1[c] == map2[c]) {
return true;
}
return false;
}
bool checkInclusion(string s1, string s2) {
for (char& c : s1) {
map1[c]++;
}
for (int i = 0, j = 0, cnt = 0; i < s2.size(); i++) {
if (check(s2[i])) cnt--;
map2[s2[i]]++;
if (check(s2[i])) cnt++;
if (i - j == s1.size()) {
if (check(s2[j])) cnt--;
map2[s2[j]]--;
if (check(s2[j])) cnt++;
j++;
}
if (cnt == map1.size()) return true;
}
return false;
}
};
Complexity
- Time: O(n)
- Space: O(n)
Top comments (0)