438. Find All Anagrams in a String
1. Description
Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
2. Example
Example 1:
Input:
s: “cbaebabacd” p: “abc”
Output:
[0, 6]
Explanation:
The substring with start index = 0 is “cba”, which is an anagram of “abc”.
The substring with start index = 6 is “bac”, which is an anagram of “abc”.
Example 2:
Input:
s: “abab” p: “ab”
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is “ab”, which is an anagram of “ab”.
The substring with start index = 1 is “ba”, which is an anagram of “ab”.
The substring with start index = 2 is “ab”, which is an anagram of “ab”.
3. Solutions
Sliding Window
m = str.size(), n = pattern.size()
Time complexity: O(m + n)
Space complexity: O(1)
class Solution {
public:
vector<int> findAnagrams(const string &str, const string &pattern) {
if (str.size() < pattern.size()) {
return {};
}
// init
array<int, letters_> letter_diff{0};
for (int i = 0; i < pattern.size(); ++i) {
++letter_diff[get_index_(str[i])];
--letter_diff[get_index_(pattern[i])];
}
int diff_count = 0;
for (int i = 0; i < letters_; ++i) {
if (letter_diff[i] != 0) {
++diff_count;
}
}
vector<int> result;
if (diff_count == 0) {
result.push_back(0);
}
// move
for (int i = 1; i + pattern.size() - 1 < str.size(); ++i) {
char old_letter = str[i - 1];
if (letter_diff[get_index_(old_letter)] == 1) {
--diff_count;
} else if (letter_diff[get_index_(old_letter)] == 0) {
++diff_count;
}
--letter_diff[get_index_(old_letter)];
char new_letter = str[i + pattern.size() - 1];
if (letter_diff[get_index_(new_letter)] == -1) {
--diff_count;
} else if (letter_diff[get_index_(new_letter)] == 0) {
++diff_count;
}
++letter_diff[get_index_(new_letter)];
if (diff_count == 0) {
result.push_back(i);
}
}
return result;
}
private:
const static int letters_ = 26;
inline int get_index_(const char letter) {
return letter - 'a';
}
};