Solution Explanation for Find All Anagrams in a String

This problem asks to find all starting indices of substrings within a string s that are anagrams of another string p. The most efficient approach is using a sliding window technique with frequency counters.

Approach:

1. Handle Trivial Cases: If the length of s is less than the length of p, there can be no anagrams, so return an empty list.

2. Frequency Counters: We use two frequency counters (arrays or hash maps):

   • cnt1: Stores the frequency of each character in p.
   • cnt2: Stores the frequency of characters in the current sliding window of s.

3. Sliding Window: We slide a window of size len(p) across s.

   • Initially, cnt2 is populated with the frequencies of characters in the first len(p) - 1 characters of s.
   • In each iteration:
     • Add the frequency of the next character in s to cnt2.
     • Check if cnt1 and cnt2 are equal. If they are, it means we've found an anagram, so add the starting index of the window to the result list.
     • Remove the frequency of the leftmost character of the window from cnt2 to maintain the window size.

4. Return Result: The function returns a list of starting indices where anagrams are found.

Time Complexity Analysis:

• The sliding window iterates through s once. Each iteration involves a constant time comparison of frequency counters (assuming constant time hash map lookups).
• Therefore, the overall time complexity is O(n), where n is the length of s.

Space Complexity Analysis:

• The space complexity is dominated by the frequency counters cnt1 and cnt2, which have a size at most equal to the number of unique characters in the alphabet (26 for lowercase English letters in this case).
• Therefore, the space complexity is O(1). This is considered constant space because it doesn't depend on the input string lengths.

Code Examples (Python, Java, C++, Go, TypeScript, Rust, C#):

The code examples in various languages demonstrate the sliding window approach. All versions follow the same logic; only syntax differs.

The Python solution utilizing Counter from the collections module makes for especially concise and readable code:

from collections import Counter
 
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ns, np = len(s), len(p)
        if ns < np: return []
        
        p_count = Counter(p)
        s_count = Counter(s[:np-1])
        output = []
        
        for i in range(np -1, ns):
            s_count[s[i]] += 1
            if s_count == p_count:
                output.append(i - np + 1)
            s_count[s[i - np + 1]] -= 1
            if s_count[s[i - np + 1]] == 0:
                del s_count[s[i-np+1]]
        return output

The Java, C++, Go, TypeScript, Rust and C# solutions use arrays of size 26 to represent the frequency counters, achieving the same functionality. They all exhibit O(n) time and O(1) space complexity. Note that the use of Arrays.equals in Java necessitates a full array comparison each time, which is still O(1) in this context.