## Algorithm

Problem Name: 438. 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 * 104`
• `s` and `p` consist of lowercase English letters.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *p;
int n;
int sz;
} res_t;
void add2res(res_t *res, int i) {
if (res->n == res->sz) {
if (res->sz == 0) res->sz = 10;
else res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(int));
//assert(res->p);
}
res->p[res->n ++] = i;
}

int* findAnagrams(char * s, char * p, int* returnSize){
res_t res = { 0 };
int cnt[26] = { 0 }, n = 0;
char c;

while (c = *(p ++)) {
cnt[c - 'a'] ++;
n ++;           // total number
}

while (c = s[tail ++]) {
i = c - 'a';
cnt[i] --;
n --;
if (cnt[i]  <  0) {
do {
j = c - 'a';
cnt[j] ++;
n ++;
} while (cnt[i]  <  0);
} else if (n == 0) {   // found one
j = c - 'a';
cnt[j] ++;
n ++;
}
}
*returnSize = res.n;
return res.p;
}
``````
Copy The Code &

Input

cmd
s = "cbaebabacd", p = "abc"

Output

cmd
[0,6]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int>res;
unordered_map < char, int>m;
for(auto c: p) m[c]++;
int i = 0, j = 0, count = p.size();
while(j  <  s.size()){
if(m[s[j++]]-- > 0) count--;
while(count == 0){
if(j - i == p.size()) res.push_back(i);
if(m[s[i++]]++ == 0) count++;
}
}
return res;
}
};
``````
Copy The Code &

Input

cmd
s = "cbaebabacd", p = "abc"

Output

cmd
[0,6]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List findAnagrams(String s, String p) {
List list = new ArrayList<>();
if (s.length()  <  p.length()) {
return list;
}
int[] pArr = new int[26];
for (char c : p.toCharArray()) {
pArr[c - 'a']++;
}
String pStr = Arrays.toString(pArr);
int start = 0;
int end = 0;
int n = s.length();
int[] sArr = new int[26];
while (end  <  (p.length() - 1)) {
sArr[s.charAt(end) - 'a']++;
end++;
}
while (end  <  n) {
sArr[s.charAt(end) - 'a']++;
end++;
if (Arrays.toString(sArr).equals(pStr)) {
}
sArr[s.charAt(start++) - 'a']--;
}
return list;
}
}
``````
Copy The Code &

Input

cmd
s = "abab", p = "ab"

Output

cmd
[0,1,2]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const findAnagrams = function (s, p) {
const slen = s.length;
const plen = p.length;
if (plen > slen) return [];
const aCode = "a".charCodeAt(0);
const count = new Array(26).fill(0);
for (let i = 0; i  <  plen; i++) count[p.charCodeAt(i) - aCode] += 1;
const res = [];
for (let i = 0; i  <  slen; i++) {
count[s.charCodeAt(i) - aCode] -= 1;
if (i >= plen - 1) {
if (i - plen >= 0) count[s.charCodeAt(i - plen) - aCode] += 1;
if (allZero(count)) res.push(i - plen + 1);
}
}
return res;
};
function allZero(count) {
for (let el of count) {
if (el !== 0) return false;
}
return true;
}
``````
Copy The Code &

Input

cmd
s = "abab", p = "ab"

Output

cmd
[0,1,2]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
out=list()
from collections import Counter
s_counter, p_counter=Counter(s[:len(p)-1]), Counter(p)
for i in range(len(p)-1,len(s)):
s_counter[s[i]]+=1
if s_counter==p_counter: out.append(i-len(p)+1)
s_counter[s[i-len(p)+1]]-=1
if s_counter[s[i-len(p)+1]]==0: del s_counter[s[i-len(p)+1]]
return out
``````
Copy The Code &

Input

cmd
s = "cbaebabacd", p = "abc"

Output

cmd
[0,6]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0438_FindAllAnagramsInAString
{
public IList < int> FindAnagrams(string s, string p)
{
var sLength = s.Length;
var pLength = p.Length;

var pCount = new int[26];
foreach (var ch in p)
pCount[ch - 'a']++;

var sCount = new int[26];
var result = new List < int>();
for (int i = 0; i  <  sLength; i++)
{
sCount[s[i] - 'a']++;
if (i >= pLength)
sCount[s[i - pLength] - 'a']--;

if (Enumerable.SequenceEqual(sCount, pCount))
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
s = "cbaebabacd", p = "abc"

Output

cmd
[0,6]