Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

An anagram of a string is a rearrangement of its characters. Two strings are anagrams of each other if they have the same characters but in different orders.

Function Signature:

from typing import List

def find_anagrams(s: str, p: str) -> List[int]:
    """
    Find all the start indices of p's anagrams in s.

    Parameters:
    - s: A string.
    - p: A non-empty string.

    Returns:
    - List[int]: A list of start indices of p's anagrams in s.
    """
    # Your code here

Example:

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]

Note:

  • The input strings consist of lowercase English letters only.
  • The order of output does not matter.

Instructions:

  • Implement the find_anagrams function to solve the problem.
  • Use Python for your implementation.
  • Provide clear comments in your code to explain the logic.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊