438.Find All Anagrams in a String
===

###### tags: `Medium`,`String`,`Hash Table`,`Sliding Window`

[438. Find All Anagrams in a String](https://leetcode.com/problems/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.

### 解答
#### C++

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> sc(26, 0), pc(26, 0), ans;
        if (s.size() < p.size()) return ans;
        for (int i = 0; i < p.size(); i++) {
            pc[p[i] - 'a']++;
            sc[s[i] - 'a']++;
        }
        if (pc == sc) ans.push_back(0);
        for (int i = p.size(); i < s.size(); i++) {
            sc[s[i] - 'a']++;
            sc[s[i - p.size()] - 'a']--;
            if (pc == sc) ans.push_back(i - p.size() + 1);
        }
        return ans;
    }
};

> [name=Yen-Chi Chen][time=Sun, Feb 5, 2023]

#### Python

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        ans = []
        if len(s) < len(p): return ans
        sc, pc = Counter(s[:len(p)]), Counter(p)
        if sc == pc: ans.append(0)
        for i in range(len(p), len(s)):
            sc[s[i]] += 1
            sc[s[i - len(p)]] -= 1
            if sc == pc: ans.append(i - len(p) + 1)
        return ans

> [name=Yen-Chi Chen][time=Sun, Feb 5, 2023]

#### Javascript

function findAnagrams(s, p) {
  let left = 0;
  let right = 0;
  let count = p.length;
  const map = [];
  const result = [];

  for (const char of p) {
    if (!map[char]) {
      map[char] = 1;
    } else {
      map[char]++;
    }
  }

  while (right < s.length) {
    if (map[s[right]] > 0) {
      count--;
    }

    map[s[right]]--;
    right++;

    if (count === 0) {
      result.push(left);
    }

    if (right - left === p.length) {
      if (map[s[left]] >= 0) {
        count++;
      }

      map[s[left]]++;
      left++;
    }
  }

  return result;
}

> [name=Marsgoat][time=Sun, Feb 5, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)