Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
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".
Constraints:
1 <= s.length, p.length <= 3 * 104s and p consist of lowercase English letters.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.
This 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.
JavaScript
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.
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.
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.
Java
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.
| Approach | Complexity |
|---|---|
| Sliding Window with Character Count | Time Complexity: O(n) where n is the length of |
| Hashmap with Two-pointer Technique | Time Complexity: O(n) where n is the length of `s`. |
Group Anagrams - Categorize Strings by Count - Leetcode 49 • NeetCode • 611,557 views views
Watch 9 more video solutions →Practice Find All Anagrams in a String with our built-in code editor and test cases.
Practice on FleetCode