0438 - Find All Anagrams in a String (Medium)

Problem Link

https://leetcode.com/problems/find-all-anagrams-in-a-string/

Problem Statement

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.

Approach 1: Sliding Window

First we build the count m2 of each character in string p. Then we keep the window size as m. If it is within the window, then we update m1 until the pointer j is out of the window. If m1 is equal to m2, then we can add the current i to the answer vector. After that, we need to move decrease m1[s[i] - 'a']] by 1 as the character s[i] will be out of the window.

• Time Complexity: $O(n + m)$

• Space Complexity: $O(1)$

C++

Written by @wingkwong

class Solution {
 public:
  vector<int> findAnagrams(string s, string p) {
      vector<int> ans, m1(26, 0), m2(26, 0);
      int n = (int) s.size(), m = (int) p.size(), j = 0;
      for (auto x : p) m2[x - 'a']++;
      for (int i = 0; i < n; i++) {
          while (j < n && j - i + 1 <= m) m1[s[j++] - 'a']++;
          if (m1 == m2) ans.push_back(i);
          m1[s[i] - 'a']--;
      }
      return ans;
  }
};

Python

Written by @wingkwong

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        # sliding window -> substring with same set of freq of chars
        ans = []
        # cnt_s: store frequency of characters in s
        # cnt_p: store frequency of characters in p
        cnt_s, cnt_p = [0] * 26, [0] * 26
        n, m = len(s), len(p)
        j = 0
        # count frequency of characters in p
        for x in p:
            cnt_p[ord(x) - ord('a')] += 1
        for i in range(n):
            # add s[j] to the window if the window is not full
            while j < n and j - i + 1 <= m:
                cnt_s[ord(s[j]) - ord('a')] += 1
                j += 1
            # check if both frequency matches
            if cnt_s == cnt_p:
                # i is the starting index of the window
                ans.append(i)
            # remove the leftmost element from the window
            cnt_s[ord(s[i]) - ord('a')] -= 1
        return ans