438. Find All Anagrams in a String

Problem

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.

Solution (Java)

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] map = new int[26];
        for (int i = 0; i < p.length(); ++i) {
            map[p.charAt(i) - 'a']++;
        }
        List<Integer> res = new ArrayList<>();
        int i = 0;
        int j = 0;
        while (i < s.length()) {
            int idx = s.charAt(i) - 'a';
            // add the new character
            map[idx]--;
            // if the length is greater than windows length, pop the left charcater in the window
            if (i >= p.length()) {
                map[s.charAt(j++) - 'a']++;
            }
            boolean finish = true;
            for (int k = 0; k < 26; k++) {
                // if it is not an anagram of string p
                if (map[k] != 0) {
                    finish = false;
                    break;
                }
            }
            if (i >= p.length() - 1 && finish) {
                res.add(j);
            }
            i++;
        }
        return res;
    }
}

Solution (Javascript)

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    let hashMap = new Map()
    for(let i = 0; i < p.length; i++) {
        if(hashMap.has(p[i])) {
            hashMap.set(p[i], hashMap.get(p[i]) + 1)
        } else {
            hashMap.set(p[i], 1)
        }
    }

    let res = new Array()
    let start = 0, end = 0
    while(end < s.length) {
        if(hashMap.get(s[end]) > 0) {
            hashMap.set(s[end], hashMap.get(s[end]) - 1)
            end++
            if(end - start == p.length) {
                res.push(start)
            }
        } else if(start == end) {
            start++
            end++
        } else {
            hashMap.set(s[start], hashMap.get(s[start]) + 1)
            start++
        }
    }
    return res
};

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).