class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int left = 0;
        int right = 0;
        Map<Character, Integer> s1Map = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            s1Map.put(c, s1Map.getOrDefault(c, 0) + 1);
        }

        Map<Character, Integer> s2Map = new HashMap<>();
        s2Map.put(s2.charAt(0), 1);
        while (right - left + 1 <= s2.length() && right < s2.length()) {
            if (!s1Map.containsKey(s2.charAt(right))) {
                left = right = right + 1;
                if (right >= s2.length()) {
                    return false;
                }
                s2Map.clear();
                s2Map.put(s2.charAt(right), s2Map.getOrDefault(s2.charAt(right), 0) + 1);
            } else if (right - left + 1 < s1.length()) {
                right += 1;
                if (right >= s2.length()) {
                    return false;
                }
                s2Map.put(s2.charAt(right), s2Map.getOrDefault(s2.charAt(right), 0) + 1);
            } else if (right - left + 1 == s1.length()) {
                if (!judge(s1Map, s2Map)) {
                    right += 1;
                    left += 1;
                    if (right >= s2.length()) {
                        return false;
                    }
                    s2Map.put(s2.charAt(right), s2Map.getOrDefault(s2.charAt(right), 0) + 1);
                    s2Map.put(s2.charAt(left - 1), s2Map.getOrDefault(s2.charAt(left - 1), 0) - 1);
                } else {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean judge(Map<Character, Integer> s1Map, Map<Character, Integer> s2Map) {
        if (s2Map.keySet().size() != s1Map.keySet().size()) {
            return false;
        }

        for (Character key :
                s2Map.keySet()) {
            if (!s1Map.containsKey(key)) {
                return false;
            } else {
                if (!s1Map.get(key).equals(s2Map.get(key))) {
                    return false;
                }
            }
        }
        return true;
    }
}