Find All Anagrams in a String

---

Find All Anagrams in a String: 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.

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 * 10^4
• s and p consist of lowercase English letters.

---

Try this Problem on your own or check similar problems:

1. Valid Anagram
2. Permutation in String
3. Minimum Window Substring

Solution:

Java

public List<Integer> findAnagrams(String s, String p) {
    if(s.length() < p.length()) return List.of();

    List<Integer> result = new ArrayList<>();
    int[] freqMap = new int[26];

    for(int i = 0; i < p.length(); ++i) freqMap[p.charAt(i) - 'a']++;
    int start = 0, end = 0, counter = 0;

    while(end < s.length()){
        if(freqMap[s.charAt(end) - 'a'] > 0) counter++;
        freqMap[s.charAt(end) - 'a']--;
        end++;

        while(counter == p.length()){
            if(end - start == p.length()){
                result.add(start);
            }
            if(freqMap[s.charAt(start) - 'a'] == 0) counter--;
            freqMap[s.charAt(start) - 'a']++;
            start++;
        }
    }

    return result;
}

JavaScript

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function (s, p) {
  if (s.length < p.length) return [];

  const result = [];
  const freqMap = new Array(26).fill(0);

  for (let i = 0; i < p.length; ++i) freqMap[p.charCodeAt(i) - 97]++;
  let start = 0;
  let end = 0;
  let counter = 0;

  while (end < s.length) {
    if (freqMap[s.charCodeAt(end++) - 97]-- > 0) counter++;
    while (counter === p.length) {
      if (end - start === p.length) {
        result.push(start);
      }
      if (freqMap[s.charCodeAt(start++) - 97]++ === 0) counter--;
    }
  }

  return result;
};

Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(s) < len(p):
            return []

        result = []
        freqMap = [0] * 26

        for char in p:
            freqMap[ord(char) - ord('a')] += 1

        start = 0
        end = 0
        counter = 0

        while end < len(s):
            if freqMap[ord(s[end]) - ord('a')] > 0:
                counter += 1
            freqMap[ord(s[end]) - ord('a')] -= 1
            end += 1

            while counter == len(p):
                if end - start == len(p):
                    result.append(start)

                if freqMap[ord(s[start]) - ord('a')] >= 0:
                    counter -= 1
                freqMap[ord(s[start]) - ord('a')] += 1
                start += 1

        return result

C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (s.length() < p.length()) return {};

        std::vector<int> result;
        std::vector<int> freqMap(26, 0);

        for (char c : p) freqMap[c - 'a']++;
        int start = 0, end = 0, counter = 0;

        while (end < s.length()) {
            if (freqMap[s[end++] - 'a']-- > 0) counter++;
            while (counter == p.length()) {
                if (end - start == p.length()) {
                    result.push_back(start);
                }
                if (freqMap[s[start++] - 'a']++ == 0) counter--;
            }
        }

        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(s) where s is the length of longer string s
• Space Complexity: O(1)

---

Explanation:

We utilize the same approach of counting the occurrences of the characters in the p string and keeping an eye on valid window (all letters present) like we did in Minimum Window Substring. We use the same template only this time checking for exact length end - start == p.length(). The time and space complexity are the same.