Solution 1: Brute Force

Intuition:

The brute force approach to solving the “Find All Anagrams in a String” problem involves generating all possible substrings of string s with the same length as string p, and for each substring, checking if it is an anagram of p.

Here’s how the brute force approach would work:

  • Iterate through string s and generate all possible substrings of length len(p).
  • For each substring, check if it is an anagram of p by comparing the sorted characters of both strings.
  • If a substring is found to be an anagram of p, record its starting index.
  • While this approach is straightforward, it is highly inefficient, especially for longer strings, as it involves generating a large number of substrings and performing sorting operations for each substring.

Solution:

from typing import List

def find_anagrams(s: str, p: str) -> List[int]:
    # Helper function to check if two strings are anagrams
    def is_anagram(s1: str, s2: str) -> bool:
        # Sort the characters of both strings and compare
        return sorted(s1) == sorted(s2)
    
    # Initialize the list to store the start indices of anagrams
    result = []
    # Length of strings s and p
    len_s, len_p = len(s), len(p)
    
    # Iterate through string s using a sliding window
    for i in range(len_s - len_p + 1):
        # Extract the substring of length len(p)
        substring = s[i:i+len_p]
        # Check if the substring is an anagram of p
        if is_anagram(substring, p):
            # If it is, record its starting index
            result.append(i)
    
    # Return the list of start indices of anagrams
    return result

# Test cases
s = "cbaebabacd"
p = "abc"
result = find_anagrams(s, p)
print(result)  # Output should be [0, 6]

s = "abab"
p = "ab"
result = find_anagrams(s, p)
print(result)  # Output should be [0, 1, 2]

Time Complexity:

While this approach provides a correct solution, it is highly inefficient, with a time complexity of O((n - m + 1) * m * log(m)), where n is the length of string s and m is the length of string p. This is because we generate (n - m + 1) substrings of length m and sort each substring, which takes O(m * log(m)) time.

Space Complexity:

During each iteration, a substring of length len(p) is generated. Therefore, the space required is O(m), where m is the length of string p.

Solution 2: Using Hashmap and Sliding Window

Intuition:

To find all the start indices of p’s anagrams in s, we can use a sliding window approach combined with a hashmap to efficiently keep track of the character frequencies in the current window.

  • First, we create a frequency map for string p to represent the count of each character in p.
  • Then, we iterate through string s using a sliding window of size len(p).
  • At each step, we update the frequency map for the current window and compare it with the frequency map of p.
  • If the frequency maps are equal, it means the current window of s is an anagram of p, so we add the start index of the window to the result.
  • Move the sliding window by one character to the right and continue the process until we reach the end of s.

Solution:

from collections import Counter
from typing import List

def find_anagrams(s: str, p: str) -> List[int]:
    # Initialize result list to store start indices of anagrams
    result = []
    # Length of strings s and p
    len_s, len_p = len(s), len(p)
    
    # Create frequency map for string p
    p_freq = Counter(p)
    # Initialize frequency map for current window
    window_freq = Counter(s[:len_p])
    
    # Check if the first window is an anagram of p
    if window_freq == p_freq:
        result.append(0)
    
    # Slide the window through string s
    for i in range(1, len_s - len_p + 1):
        # Update the window frequency map
        window_freq[s[i - 1]] -= 1
        if window_freq[s[i - 1]] == 0:
            del window_freq[s[i - 1]]
        window_freq[s[i + len_p - 1]] += 1
        
        # Check if the current window is an anagram of p
        if window_freq == p_freq:
            result.append(i)
    
    return result

# Test cases
s = "cbaebabacd"
p = "abc"
result = find_anagrams(s, p)
print(result)  # Output should be [0, 6]

s = "abab"
p = "ab"
result = find_anagrams(s, p)
print(result)  # Output should be [0, 1, 2]

Time Complexity:

  • The time complexity of this approach is O(n), where n is the length of string s.
  • We iterate through string s only once, and the operations inside the loop take constant time.
  • Note that the comparison of the two frequency maps is also considered to take constant time because it takes time proportional to the size of the maps and each map could contain only a maximum of 26 elements (the number of unique lowercase English letters).

Space Complexity:

  • The space complexity is O(1) because the frequency maps (Counter objects) have a constant size determined by the number of unique lowercase English letters.