# Find All Anagrams in a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-all-anagrams-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/find-all-anagrams-in-a-string
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
**Companies:** [Bolt](https://scaleengineer.com/companies/bolt), [Intuit](https://scaleengineer.com/companies/intuit), [Snowflake](https://scaleengineer.com/companies/snowflake), [Yandex](https://scaleengineer.com/companies/yandex), [Turing](https://scaleengineer.com/companies/turing), [Databricks](https://scaleengineer.com/companies/databricks), [Revolut](https://scaleengineer.com/companies/revolut), [Splunk](https://scaleengineer.com/companies/splunk)
---
## Problem
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**.

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

# Approaches
## Brute Force with Sorting
This approach iterates through every possible substring of `s` that has the same length as `p`. For each substring, it checks if it's an anagram of `p` by sorting both the substring and `p` and comparing the results.
**Time:** O((n - m) * m log m), where `n` is the length of `s` and `m` is the length of `p`. The loop runs `n - m` times. Inside the loop, creating a substring takes O(m) and sorting it takes O(m log m). · **Space:** O(m), where `m` is the length of the pattern string `p`. This space is required to store the character arrays for `p` and the current substring.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient due to the repeated sorting of substrings.; Likely to result in a 'Time Limit Exceeded' error on most online judges for larger inputs.
### Explanation
The core idea is that two strings are anagrams if and only if their sorted versions are identical. We first sort the pattern string `p` once to have a reference. Then, we iterate through the string `s` from the beginning up to the last possible starting point for a substring of `p`'s length. In each iteration, we extract the substring, convert it to a character array, sort it, and then compare this sorted character array with the pre-sorted pattern `p`'s character array. If they match, we've found an anagram, and we add the starting index of the substring to our result list.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        List<Integer> result = new ArrayList<>();
        if (n < m) {
            return result;
        }

        char[] pChars = p.toCharArray();
        Arrays.sort(pChars);

        for (int i = 0; i <= n - m; i++) {
            String sub = s.substring(i, i + m);
            char[] sChars = sub.toCharArray();
            Arrays.sort(sChars);
            if (Arrays.equals(pChars, sChars)) {
                result.add(i);
            }
        }
        return result;
    }
}
```
### Algorithm
- Get the lengths of `s` and `p`, let's say `n` and `m`.
- If `n < m`, return an empty list as no anagram is possible.
- Convert `p` to a character array and sort it. This sorted array will be our reference.
- Initialize an empty list `result` to store the starting indices.
- Loop with an index `i` from `0` to `n - m`.
- In the loop, get the substring of `s` of length `m` starting at `i`.
- Convert this substring to a character array and sort it.
- Compare the sorted substring's character array with the sorted `p`'s character array.
- If they are identical, add `i` to the `result` list.
- After the loop, return the `result` list.

## Brute Force with Character Frequency Map
This is an optimization over the sorting approach. Instead of sorting, we check for anagrams by comparing character frequency counts. We iterate through all substrings of `s` with length `p`, and for each one, we build a frequency map and compare it to the frequency map of `p`.
**Time:** O((n - m) * m). The outer loop runs `n - m` times, and the inner loop to build the frequency map for the substring runs `m` times. · **Space:** O(1) or O(k) where `k` is the alphabet size (26 in this case). We use two fixed-size arrays for the frequency maps, so the space is constant.
**Pros:** More efficient than the sorting approach.; Avoids the expensive sorting operation.
**Cons:** Still inefficient due to redundant computations.; The frequency map for each window is built from scratch, while adjacent windows share most of their characters.
### Explanation
Two strings are anagrams if they have the same characters with the same frequencies. We can represent these frequencies using a hash map or, since the characters are lowercase English letters, a simple array of size 26. First, we compute the frequency map for the pattern `p`. Then, we iterate through `s`, considering each window of size `m` (length of `p`). For each window (substring), we compute its own character frequency map from scratch. We then compare this new frequency map with the one we created for `p`. If the two maps are identical, the substring is an anagram, and we record its starting index. This avoids the `O(m log m)` sorting cost, replacing it with a more efficient `O(m)` cost for building the frequency map.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        List<Integer> result = new ArrayList<>();
        if (n < m) {
            return result;
        }

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

        for (int i = 0; i <= n - m; i++) {
            int[] sFreq = new int[26];
            for (int j = 0; j < m; j++) {
                sFreq[s.charAt(i + j) - 'a']++;
            }
            if (Arrays.equals(pFreq, sFreq)) {
                result.add(i);
            }
        }
        return result;
    }
}
```
### Algorithm
- Get the lengths of `s` and `p`, `n` and `m`.
- If `n < m`, return an empty list.
- Create a frequency map for `p` (e.g., an array `pFreq` of size 26 for lowercase English letters).
- Initialize an empty list `result`.
- Loop with an index `i` from `0` to `n - m`.
- In the loop, create a frequency map for the substring `s.substring(i, i + m)` (e.g., an array `sFreq` of size 26).
- Compare `pFreq` and `sFreq`.
- If they are identical, add `i` to the `result` list.
- After the loop, return `result`.

## Sliding Window with Frequency Map
This is the most optimal approach. It uses the sliding window technique to avoid redundant calculations. We maintain a window of size `p.length()` and a frequency map of the characters within that window. As we slide the window one character at a time, we efficiently update the frequency map in O(1) time instead of rebuilding it.
**Time:** O(n), where `n` is the length of string `s`. We initialize the maps in `O(m)` time. The main loop runs `n - m` times. Inside the loop, operations are constant time, except for `Arrays.equals`, which takes `O(k)` where `k` is the alphabet size (26). So, the total time is `O(m + (n-m)*k)`. Since `k` is constant, this simplifies to `O(n)`. · **Space:** O(1) or O(k) where `k` is the alphabet size (26). We use two fixed-size arrays for the frequency maps, which does not depend on the input string lengths.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for this problem.
**Cons:** Slightly more complex to implement than the brute-force approaches.
### Explanation
The key insight is that when we slide the window from `[i, i+m-1]` to `[i+1, i+m]`, we only need to account for two character changes: the character `s[i]` leaving the window and the character `s[i+m]` entering it. We start by creating a frequency map for `p` and for the initial window in `s` (from index 0 to `m-1`). We check if this first window is an anagram. Then, we iterate from `m` to the end of `s`. In each step, we slide the window by decrementing the count of the character that is now outside the window and incrementing the count of the new character entering the window. After each update, we compare the window's frequency map with `p`'s frequency map. If they match, we've found an anagram and record the new window's starting index. This way, each character in `s` is visited a constant number of times, leading to a linear time complexity.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n = s.length();
        int m = p.length();
        List<Integer> result = new ArrayList<>();
        if (n < m) {
            return result;
        }

        int[] pFreq = new int[26];
        int[] sWindowFreq = new int[26];

        // Build frequency map for p and the first window in s
        for (int i = 0; i < m; i++) {
            pFreq[p.charAt(i) - 'a']++;
            sWindowFreq[s.charAt(i) - 'a']++;
        }

        // Check if the first window is an anagram
        if (Arrays.equals(pFreq, sWindowFreq)) {
            result.add(0);
        }

        // Slide the window across the rest of s
        for (int i = m; i < n; i++) {
            // Add the new character to the window
            sWindowFreq[s.charAt(i) - 'a']++;
            // Remove the character that's leaving the window
            sWindowFreq[s.charAt(i - m) - 'a']--;

            // Check if the current window is an anagram
            if (Arrays.equals(pFreq, sWindowFreq)) {
                result.add(i - m + 1);
            }
        }

        return result;
    }
}
```
### Algorithm
- Get lengths `n` and `m`. If `n < m`, return an empty list.
- Create two frequency maps (arrays of size 26), `pFreq` and `sWindowFreq`.
- Populate `pFreq` using characters from `p`.
- Populate `sWindowFreq` using characters from the first `m` characters of `s`.
- Initialize an empty list `result`.
- Compare `pFreq` and `sWindowFreq`. If they are equal, add `0` to `result`.
- Loop with an index `i` from `m` to `n - 1`.
- In the loop, update `sWindowFreq`:
  - Increment the count for the new character `s.charAt(i)`.
  - Decrement the count for the old character `s.charAt(i - m)`.
- Compare `pFreq` and `sWindowFreq`. If they are equal, add the start index of the current window (`i - m + 1`) to `result`.
- After the loop, return `result`.

# Solutions
### CSharp

```csharp
public class Solution { public IList < int > FindAnagrams ( string s , string p ) { int m = s . Length , n = p . Length ; IList < int > ans = new List < int >(); if ( m < n ) { return ans ; } int [] cnt1 = new int [ 26 ]; int [] cnt2 = new int [ 26 ]; for ( int i = 0 ; i < n ; ++ i ) { ++ cnt1 [ p [ i ] - 'a' ]; } for ( int i = 0 , j = 0 ; i < m ; ++ i ) { int k = s [ i ] - 'a' ; ++ cnt2 [ k ]; while ( cnt2 [ k ] > cnt1 [ k ]) { -- cnt2 [ s [ j ++] - 'a' ]; } if ( i - j + 1 == n ) { ans . Add ( j ); } } return ans ; } }
```

### Java

```java
class Solution {
public
  List<Integer> findAnagrams(String s, String p) {
    int m = s.length(), n = p.length();
    List<Integer> ans = new ArrayList<>();
    if (m < n) {
      return ans;
    }
    int[] cnt1 = new int[26];
    for (int i = 0; i < n; ++i) {
      ++cnt1[p.charAt(i) - 'a'];
    }
    int[] cnt2 = new int[26];
    for (int i = 0; i < n - 1; ++i) {
      ++cnt2[s.charAt(i) - 'a'];
    }
    for (int i = n - 1; i < m; ++i) {
      ++cnt2[s.charAt(i) - 'a'];
      if (Arrays.equals(cnt1, cnt2)) {
        ans.add(i - n + 1);
      }
      --cnt2[s.charAt(i - n + 1) - 'a'];
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> findAnagrams(string s, string p) {
    int m = s.size(), n = p.size();
    vector<int> ans;
    if (m < n) {
      return ans;
    }
    vector<int> cnt1(26);
    for (char &c : p) {
      ++cnt1[c - 'a'];
    }
    vector<int> cnt2(26);
    for (int i = 0; i < n - 1; ++i) {
      ++cnt2[s[i] - 'a'];
    }
    for (int i = n - 1; i < m; ++i) {
      ++cnt2[s[i] - 'a'];
      if (cnt1 == cnt2) {
        ans.push_back(i - n + 1);
      }
      --cnt2[s[i - n + 1] - 'a'];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]: m, n = len(s), len(p) ans = [] if m < n: return ans cnt1 = Counter(p) cnt2 = Counter(s[: n - 1]) for i in range(n - 1, m): cnt2[s[i]] += 1 if cnt1 == cnt2: ans . append(i - n + 1) cnt2[s[i - n + 1]] -= 1 return ans

```