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.
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".
Solution
class Solution {
public:
vector<int> findAnagrams(string &s, string &p) {
if (s.empty() || p.empty() || s.size() < p.size()) return vector<int>();
int counter_p[26], counter_s[26];
compute_counter(p, 0, p.size(), counter_p);
compute_counter(s, 0, p.size(), counter_s);
vector<int> indice;
const int n = s.size() - p.size() + 1;
indice.reserve(n);
if (equal(counter_p, counter_s)) indice.emplace_back(0);
for (int i = 1; i < n; ++i) {
--counter_s[s[i - 1] - 'a'];
++counter_s[s[i + p.size() - 1] - 'a'];
if (equal(counter_p, counter_s)) indice.emplace_back(i);
}
return indice;
}
inline void compute_counter(string &s, int begin, int end, int *counter) {
memset(counter, 0, sizeof(int) * 26);
for (int i = begin; i < end; ++i) ++counter[s[i] - 'a'];
}
inline bool equal(int *c1, int *c2) {
for (int i = 0; i < 26; ++i) {
if (c1[i] != c2[i]) return false;
}
return true;
}
};
