// https://leetcode.com/problems/find-all-anagrams-in-a-string/
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> l = new LinkedList<>();
        if(s.length() < p.length()) return l;
        int[] sampleMap = makeMap(p);
        int window = p.length();
        int[] currentMap = makeMap(s.substring(0, window));

        int i = window;

        if(isMapEqual(sampleMap, currentMap)){
            l.add(i-window);
        }
        while(i < s.length()){
            --currentMap[s.charAt(i-window) - 'a'];
            ++currentMap[s.charAt(i) - 'a'];
            if(isMapEqual(sampleMap, currentMap)){
                l.add(i-window+1);
            }
            ++i;
        }
        return l;
    }


    static int[]  makeMap(String s){
        int[] map = new int[26];

            for(int i=0;i<map.length;++i){
                map[i] = 0;
            }

            for(int i=0;i<s.length();++i){
                map[s.charAt(i) - 'a'] += 1;
            }
        return map;
    }
    static boolean isMapEqual(int [] a, int[] b){
        if(a.length != b.length) return false;
        for(int i=0;i<a.length;++i){
            if(a[i] != b[i]) return false;
        }
        return true;
    }
}


//////////////////////////////////////////////
// more efficient solution:
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        Map<Character, Integer> mymap = new HashMap<>();
        List<Integer> res = new LinkedList<>();
        for(char c : p.toCharArray()){
            mymap.put(c, mymap.getOrDefault(c, 0) + 1);
        }
        int start = 0, end = 0, count = mymap.size(), len = s.length();
        while(end < len){
            char r = s.charAt(end);
            mymap.put(r, mymap.getOrDefault(r, 0)-1);
            if(mymap.get(r) == 0) count--;
            end++;


            while(count == 0){
                if(end-start == p.length()){
                    res.add(start);
                }


                char x = s.charAt(start);
                mymap.put(x, mymap.getOrDefault(x, 0) + 1);
                if(mymap.get(x) > 0) count++;
                start++;
            }
        }
        return res;
    }
}