Find All Anagrams in a String

Problem Statement

Given two strings, s (the main string) and p (the pattern), the task is to find all starting indices within s where a substring is an anagram of p. An anagram of a string is another string that contains the same characters, only the order of characters can be different. The function must return a list of starting indices for each substring of s that is an anagram of p. The output list doesn't need to be in any particular order.

Examples

Example 1

Input:

s = "cbaebabacd", p = "abc"

Output:

[0,6]

Explanation:

The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2

Input:

s = "abab", p = "ab"

Output:

[0,1,2]

Explanation:

The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

Constraints

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

Approach and Intuition

The problem asks for finding all start positions where the anagram of the pattern p appears in the string s. Here's the overall approach:

1. Character Count Comparison: At the core, the problem can be solved by comparing character frequencies between the pattern p and substrings of s of the same length as p.

2. Sliding Window Technique: This problem is efficiently handled using a sliding window and a hashmap (or array) to count characters:

   • Initialize a fixed size window equal to the length of p that slides over s.
   • Use a hash map to count the frequency of each character in the pattern p.
   • As the window slides over s, compare if the character count of the window matches the character count of p.

3. Handle Window Slide:

   • When the window slides right, decrease the count of the character that is left out of the window and increase the count of the new character that is included in the window.
   • After adjusting counts, compare the new window's character count with p's count.

4. Efficiency: Each comparison of the counts has a time complexity of O(1) if implemented using fixed-size arrays (given the constraint of lowercase English letters), ensuring overall time complexity remains manageable even as input size grows.

These simple steps illustrate the methodology to solve the problem, acknowledging the constraints and nature of input (all lowercase English letters, making fixed-size frequency arrays a feasible solution). This solution does not need to check character counts across the entire window every time but only updates the counts as needed, which is more efficient in contrast to naive approaches.

Solutions

class Solution {
  public List<Integer> searchAnagrams(String str, String pattern) {
    int strLen = str.length(), patLen = pattern.length();
    if (strLen < patLen) return new ArrayList<>();

    int [] patFrequency = new int[26];
    int [] strFrequency = new int[26];
    for (char c : pattern.toCharArray()) {
      patFrequency[c - 'a']++;
    }

    List<Integer> resultList = new ArrayList<>();
    for (int i = 0; i < strLen; ++i) {
      strFrequency[str.charAt(i) - 'a']++;
      if (i >= patLen) {
        strFrequency[str.charAt(i - patLen) - 'a']--;
      }
      if (Arrays.equals(patFrequency, strFrequency)) {
        resultList.add(i - patLen + 1);
      }
    }
    return resultList;
  }
}