567. Permutation in String
1. 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.
2. Example
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
3. Constraints
- 1 <= s1.length, s2.length <= $10^4$
- s1 and s2 consist of lowercase English letters.
4. Solutions
Sliding Window
n = str2.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
bool checkInclusion(const string &str1, const string &str2) {
if (str2.size() < str1.size()) {
return false;
}
array<int, 26> letters_diff{0}; // str2 - str1
for (int i = 0; i < str1.size(); ++i) {
--letters_diff[get_index_(str1[i])];
++letters_diff[get_index_(str2[i])];
}
int diff_count = 0;
for (int i = 0; i < letters_diff.size(); ++i) {
if (letters_diff[i] != 0) {
++diff_count;
}
}
if (diff_count == 0) {
return true;
}
for (int left = 0, right = str1.size(); right < str2.size(); ++left, ++right) {
if (str2[left] == str2[right]) {
--letters_diff[get_index_(str2[left])];
++letters_diff[get_index_(str2[right])];
if (letters_diff[get_index_(str2[left])] == 0) {
--diff_count;
} else if (letters_diff[get_index_(str2[left])] == -1) {
++diff_count;
}
if (letters_diff[get_index_(str2[right])] == 0) {
--diff_count;
} else if (letters_diff[get_index_(str2[right])] == 1) {
++diff_count;
}
}
if (diff_count == 0) {
return true;
}
}
return false;
}
private:
inline int get_index_(char letter) {
return letter - 'a';
}
};