LeetCode : 438. Find All Anagrams in a String

[congr]

https://leetcode.com/problems/find-all-anagrams-in-a-string/

[congr]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList();

        int L = p.length();
        int N = s.length();

        char[] pc = p.toCharArray();
        Arrays.sort(pc);

        for (int i = 0; i <= N-L; i++) {
            String t = s.substring(i, i+L);
            char[] tc = t.toCharArray();
            Arrays.sort(tc);

            if (Arrays.equals(pc, tc)) list.add(i);
        }

        return list;
    }
}

[congr]

O(N)

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList();
        int M = p.length(), N = s.length();
        if (M > N) return list;

        Map<Character, Integer> map = new HashMap();            
        for (char c : p.toCharArray()) map.merge(c, -1, Integer::sum);

        int found = 0;
        for (int b = 0, e = 0; e < N; e++) {
            if (map.merge(s.charAt(e), 1, Integer::sum) <= 0) found++;

            while(found == M) {
                if (e-b+1 == M) list.add(b); // !!! length check
                if (map.merge(s.charAt(b), -1, Integer::sum) < 0) found--;                
                b++;
            }
        }

        return list;
    }
}