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.
1def findAnagrams(s, p):
2 from collections import Counter
3 p_count = Counter(p)
4 s_count = Counter(s[:len(p) - 1])
5 result = []
6
7 for i in range(len(p) - 1, len(s)):
8 s_count[s[i]] += 1 # Include the new character in the window
9 if s_count == p_count: # Compare window with p
10 result.append(i - len(p) + 1) # Append the start index
11 s_count[s[i - len(p) + 1]] -= 1 # Remove the character sliding out of the window
12 if s_count[s[i - len(p) + 1]] == 0:
13 del s_count[s[i - len(p) + 1]] # Clean up the count dictionary
14
15 return resultThis Python solution initializes a counter for the string p and a sliding window counter for s of length equivalent to p. As the window slides over s, we update the count of characters within this window. If the window's character frequency matches with that of p, it implies an anagram is found and we record the starting index.
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.
1import java.util.*;
2
3
This Java approach employs two arrays to store the frequency of each character. We iterate over s with a sliding window of size equal to p, updating these arrays accordingly. If both frequency arrays match at any point, it indicates the presence of an anagram.