Find All Anagrams in a String

This challenge involves identifying all starting indices of substrings within a larger string that are anagrams of a given smaller string. This is a common problem in string manipulation and pattern matching, with applications in areas like text analysis, search algorithms, and data validation.

Problem Description

Given two strings, s (the larger string) and p (the pattern string), your task is to find all the start indices in s where a substring of s of the same length as p is an anagram of p.

An anagram of a string is another string that contains the same characters, only the order of characters can be different.

Key Requirements:

• You must return a list of all starting indices in s where an anagram of p is found.
• The order of the indices in the output list does not matter.
• The substrings to consider in s must have the exact same length as p.

Expected Behavior: If s = "cbaebabacd" and p = "abc", the substrings of s with length 3 are:

• "cba" (index 0) - anagram of "abc"
• "bae" (index 1) - not an anagram of "abc"
• "eba" (index 2) - not an anagram of "abc"
• "bab" (index 3) - not an anagram of "abc"
• "aba" (index 4) - not an anagram of "abc"
• "bac" (index 5) - anagram of "abc"
• "aca" (index 6) - not an anagram of "abc"
• "cad" (index 7) - not an anagram of "abc"

Therefore, the expected output would be [0, 6].

Edge Cases:

• If p is longer than s, no anagrams can be found.
• If p is an empty string, what should the output be? (Consider this carefully).
• If s is an empty string, no anagrams can be found.
• Strings containing only one distinct character.
• Strings with repeated characters.

Examples

Example 1:

Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation:
The substring starting at index 0 is "cba", which is an anagram of "abc".
The substring starting at index 6 is "bac", which is an anagram of "abc".

Example 2:

Input: s = "abab", p = "ab"
Output: [0, 1, 2]
Explanation:
The substring starting at index 0 is "ab", which is an anagram of "ab".
The substring starting at index 1 is "ba", which is an anagram of "ab".
The substring starting at index 2 is "ab", which is an anagram of "ab".

Example 3:

Input: s = "a", p = "a"
Output: [0]
Explanation: The substring starting at index 0 is "a", which is an anagram of "a".

Example 4:

Input: s = "abc", p = "d"
Output: []
Explanation: No substring of "abc" is an anagram of "d".

Constraints

• 1 <= s.length, p.length <= 10^4
• s and p consist of lowercase English letters.
• The time complexity should be efficient, ideally O(N) where N is the length of s.

Notes

• To determine if two strings are anagrams, you can compare their character counts.
• Consider how to efficiently update character counts as you slide a window of size p.length across s.
• Think about data structures that can help you quickly compare character frequencies.