438. Find All Anagrams in a Stri

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

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".

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
bool compare(int* sCnt, int* pCnt, int size) {
    for (int i = 0; i < size; i++) {
        if (sCnt[i] != pCnt[i]) return false;
    }
    return true;
}

int* findAnagrams(char* s, char* p, int* returnSize) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int* res = (int*) malloc(sLen * sizeof(int));
    *returnSize = 0;
    if (sLen < pLen) return res;
    int pCnt[26];
    int sCnt[26];
    memset(pCnt, 0, 26 * sizeof(int));
    memset(sCnt, 0, 26 * sizeof(int));
    for (int i = 0; i < pLen; i++) {
        pCnt[p[i] - 'a']++;
    }
    for (int i = 0; i < pLen; i++) {
        sCnt[s[i] - 'a']++;
    }
    if (true == compare(sCnt, pCnt, 26)) {
        res[*returnSize] = 0;
        *returnSize += 1;
    }
    for (int i = pLen; i < sLen; i++) {
        sCnt[s[i - pLen] - 'a']--;
        sCnt[s[i] - 'a']++;
        if (true == compare(sCnt, pCnt, 26)) {
            res[*returnSize] = i - pLen + 1;
            *returnSize += 1;
        }
    }
    return res;
}