Katkat
Back

Find all anagram start indices

DatabricksSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to efficiently detect pattern matches within a stream or string using a sliding window technique and frequency mapping.

Problem Statement

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.

An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Function Signature

def find_anagrams(s: str, p: str) -> List[int]:

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.

Examples

Example 1:

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

Example 2:

  • Input: s = "abab", p = "ab"
  • Output: [0, 1, 2]
  • Explanation: The substrings are "ab", "ba", and "ab", all of which are anagrams of "ab".

Edge Cases

  • len(p) > len(s): Should return an empty list.
  • Empty strings: While the constraints define lengths >= 1, consider how your logic handles p being longer than s.
  • All characters are the same: Ensure the window counts handle recurring character frequencies correctly.

Hints

Hint 1

Instead of sorting every substring of length len(p) (which is O(N * M log M)), use a frequency counter (hash map or integer array of size 26) to track character counts.

Hint 2

Use a sliding window approach to maintain a frequency map of the current substring of length len(p), updating it by adding the character entering the window and removing the one exiting.

Hint 3

Compare the frequency map of the current window to the target frequency map of `p` at each step; if they match, the starting index of the window is a valid result.

Follow-up questions

  • How would you optimize the space complexity if the alphabet size were significantly larger (e.g., Unicode characters)?
  • Can you modify your solution to find the shortest substring in `s` that contains all characters of `p` (the Minimum Window Substring problem)?
  • How does your algorithm's performance change if `p` is extremely small versus when it is nearly the same length as `s`?