Frontend School

Find All Anagrams of a Pattern in Text

DSA
medium

Find All Anagrams of a Pattern in Text

Medium
String
Sliding Window
Hash Map

Overview

In text processing and data analysis, efficiently searching for patterns is a fundamental task. One common requirement is to find all occurrences of a specific pattern, even if its characters are rearranged. This problem challenges you to implement an algorithm that identifies all starting positions within a larger text where an anagram of a given pattern string can be found. This capability is crucial for features like advanced search, plagiarism detection, and genomic sequence analysis.

What you need to do / Task

Your task is to implement a function findAnagrams that takes two strings, s (the text) and p (the pattern), and returns a list of all starting indices in s where an anagram of p exists. The order of characters does not matter for an anagram, only their counts.

Input & output

  • Input:
    • s: A string representing the text to search within.
    • p: A string representing the pattern whose anagrams we are looking for.
  • Output:
    • An array of numbers (integers), where each number is a 0-based starting index in s where an anagram of p is found. If no such anagrams exist, return an empty array.

Clarifications

  • Both s and p will consist of lowercase English letters only.
  • The comparison for anagrams is case-sensitive (though not relevant here since all are lowercase).
  • If p is longer than s, no anagrams can exist; your function should handle this by returning an empty array.
  • An empty p string is not expected as per constraints.

Examples

1

Example 1

Input:

s = "cbaebabacd", p = "abc"

Output:

[0,6]

Note:

The substring s[0...2] is "cba", which is an anagram of "abc". The substring s[6...8] is "bac", which is an anagram of "abc".

2

Example 2

Input:

s = "abab", p = "ab"

Output:

[0,1,2]

Note:

The substring s[0...1] is "ab", an anagram of "ab". The substring s[1...2] is "ba", an anagram of "ab". The substring s[2...3] is "ab", an anagram of "ab".

3

Example 3

Input:

s = "abc", p = "def"

Output:

[]

Note:

No anagram of "def" exists in "abc".

4

Example 4

Input:

s = "a", p = "a"

Output:

[0]

Note:

The substring s[0...0] is "a", an anagram of "a".

Constraints

Constraints & assumptions

  • 1 <= s.length <= 10^5
  • 1 <= p.length <= s.length
  • Both s and p consist of lowercase English letters ('a' through 'z').

What interviewers evaluate

  • Algorithm Correctness: Does the solution correctly identify all anagrams and their starting indices under various conditions?
  • Time and Space Complexity: Is the solution efficient, ideally achieving optimal linear time complexity with minimal auxiliary space?
  • Code Quality: Is the code well-structured, readable, and maintainable, adhering to good programming practices?
  • Problem-Solving Approach: Can the candidate clearly articulate their thought process, explain trade-offs, and adapt if edge cases are identified?

Loading editor...