Frontend School

Find All Anagrams of a Pattern in a String

DSA
medium

Find All Anagrams of a Pattern in a String

Medium
String
Sliding Window
Hash Map

Overview

At Amazon, efficient text processing is crucial for services like search indexing, content moderation, and fraud detection. One common task is identifying patterns within large text bodies. This problem challenges you to find all occurrences of a given pattern's anagrams within a larger string. Your solution will contribute to ensuring fast and accurate pattern matching, a key component in maintaining high-quality service performance.

What you need to do / Task

Implement a function findAllAnagrams that identifies all starting indices in a given string s where an anagram of another string p exists.

  1. The function should take two string arguments: s (the main text) and p (the pattern).
  2. It should return an array of numbers, representing the starting indices in s where an anagram of p is found.
  3. The order of indices in the returned array does not matter.

Input & output

  • Input:
    • s: A string representing the main text to search within.
    • p: A string representing the pattern whose anagrams we need to find.
  • Output: An array of numbers, where each number is a starting index in s where an anagram of p is found.

Clarifications

  • Both s and p will consist only of lowercase English letters ('a' through 'z').
  • The length of p will always be less than or equal to the length of s.

Examples

1

Example 1

Input:

s = "cbaebabacd", p = "abc"

Output:

[0,6]

Note:

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".

2

Example 2

Input:

s = "abab", p = "ab"

Output:

[0,1,2]

Note:

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".

3

Example 3

Input:

s = "abacb", p = "abc"

Output:

[1]

Note:

The substring starting at index 1 is "bac", which is an anagram of "abc".

Constraints

Constraints & assumptions

  • 1 <= s.length, p.length <= 10^5
  • p.length <= s.length
  • s and p consist of lowercase English letters only.

What interviewers evaluate

  • Correctness: The solution accurately identifies all anagrams and their starting indices.
  • Efficiency: The solution achieves optimal time complexity (e.g., O(N) where N is s.length) and uses minimal additional space.
  • Clarity & Readability: The code is well-structured, easy to understand, and follows good coding practices.
  • Problem-solving approach: Demonstrates clear thought process, including identifying the sliding window pattern and effectively using frequency maps to track character counts.

Loading editor...