Find All Anagrams in a String

Problem Description

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.

Key Insights

• An anagram is a rearrangement of the characters of a string.
• To find anagrams efficiently, we can use a sliding window approach combined with character counting.
• We can maintain a count of characters for the string p and compare it with counts of characters in substrings of s of the same length.

Space and Time Complexity

Time Complexity: O(n), where n is the length of string s.
Space Complexity: O(1), as we are using a fixed size array for character counts.

Solution

We utilize a sliding window approach where we maintain a count of character frequencies for the string p and compare it with the character frequencies of the current window in s. By sliding the window one character at a time and updating the counts, we can efficiently determine when we have an anagram of p.

Code Solutions