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 * 104sandpconsist 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;
int head, tail, i, j;
char c;
while (c = *(p ++)) {
cnt[c - 'a'] ++;
n ++; // total number
}
head = tail = 0;
while (c = s[tail ++]) {
i = c - 'a';
cnt[i] --;
n --;
if (cnt[i] < 0) {
do {
c = s[head ++];
j = c - 'a';
cnt[j] ++;
n ++;
} while (cnt[i] < 0);
} else if (n == 0) { // found one
add2res(&res, head);
c = s[head ++]; // push one out from head
j = c - 'a';
cnt[j] ++;
n ++;
}
}
*returnSize = res.n;
return res.p;
}
Input
s = "cbaebabacd", p = "abc"
Output
[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;
}
};
Input
s = "cbaebabacd", p = "abc"
Output
[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)) {
list.add(start);
}
sArr[s.charAt(start++) - 'a']--;
}
return list;
}
}
Input
s = "abab", p = "ab"
Output
[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;
}
Input
s = "abab", p = "ab"
Output
[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
Input
s = "cbaebabacd", p = "abc"
Output
[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))
result.Add(i - pLength + 1);
}
return result;
}
}
}
Input
s = "cbaebabacd", p = "abc"
Output
[0,6]