Sponsored
Sponsored
This approach utilizes a sliding window technique combined with character count comparisons to efficiently find all anagrams of the string p within the string s. By maintaining a window of length equal to p as we iterate through s, and by checking the frequency of characters within this window with the frequency of characters in p, we can determine if the substring is an anagram.
Time Complexity: O(n) where n is the length of s, because we iterate over `s` once.
Space Complexity: O(1) since the size of the character frequency array is fixed with respect to the alphabet.
1function findAnagrams(s, p) {
2 const pCount = new Array(26).fill(0);
3 const sCount = new Array(26).fill(0);
4 const result = [];
5 const aCharCode = 'a'.charCodeAt(0);
6
7 for (const char of p) {
8 pCount[char.charCodeAt(0) - aCharCode]++;
9 }
10
11 for (let i = 0; i < s.length; i++) {
12 sCount[s[i].charCodeAt(0) - aCharCode]++;
13
14 if (i >= p.length) {
15 sCount[s[i - p.length].charCodeAt(0) - aCharCode]--;
16 }
17
18 if (arraysEqual(pCount, sCount)) {
19 result.push(i - p.length + 1);
20 }
21 }
22 return result;
23}
24
25function arraysEqual(arr1, arr2) {
26 for (let i = 0; i < 26; i++) {
27 if (arr1[i] !== arr2[i]) return false;
28 }
29 return true;
30}This JavaScript solution uses two frequency arrays to keep count of the characters in p and a sliding window in s. The window size is maintained to be the length of p. As the window slides through s, we check if the two frequency arrays (for the window and p) are equal, indicating an anagram found.
This approach leverages hashmaps (or dictionaries) and a two-pointer technique to find the anagrams of p in s. We maintain counts of characters using hashmaps and adjust them as the two pointers traverse through s.
Time Complexity: O(n) where n is the length of `s`.
Space Complexity: O(1) if considering character frequency hashmaps to have at most 26 entries.
1#include <vector>
2#include <string>
3#include <unordered_map>
4using namespace std;
5
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> p_count, s_count;
vector<int> result;
int pl = p.size(), sl = s.size();
if (pl > sl) return result;
for (int i = 0; i < pl; i++) {
p_count[p[i]]++;
s_count[s[i]]++;
}
for (int i = pl; i < sl; i++) {
if (p_count == s_count) {
result.push_back(i - pl);
}
s_count[s[i]]++;
s_count[s[i - pl]]--;
if (s_count[s[i - pl]] == 0) {
s_count.erase(s[i - pl]);
}
}
if (p_count == s_count) {
result.push_back(sl - pl);
}
return result;
}This C++ solution uses unordered maps to count occurrences of characters in both p and the sliding window within s. We first count characters in the initial window and then slide the window through s. During each step, we update the counts by adding the new character and removing the old one (left behind) and check if the current window matches the character count of p.