567. Permutation in String

T: o(n)

S: o(n)

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> needs = new HashMap<>();
        for (char c : s1.toCharArray()) {
            needs.put(c, needs.getOrDefault(c, 0)+1);
        }
        
        int left = 0;
        int right = 0;
        int matched = 0;
        
        while (right < s2.length()) {
            char rightChar = s2.charAt(right);
            right++;
            if (needs.containsKey(rightChar)) {
                needs.put(rightChar, needs.getOrDefault(rightChar, 0)-1);
                if (needs.get(rightChar) == 0) {
                    matched++;
                }
            }
            while (matched == needs.size()) {
                if (right - left == s1.length()) { // when len match to s1 -> true
                    return true;
                }
                char leftChar = s2.charAt(left);
                left++;
                if (needs.containsKey(leftChar)) {
                    if (needs.get(leftChar) == 0) {
                        matched--;
                    }
                    needs.put(leftChar, needs.getOrDefault(leftChar, 0)+1);
                }
            }
        }
        return false;
    }
}

/*
s1 = "ab" or "ba"
so we can use sliding win to find in s2

this window size must equals to s1, because we only allow s1's permutation


still need a map for s1 (char, count) buid needs map
when current in needs, needs[current]--, if needs[current] == 0 -> matched++

"eidbaooo"
 l
     r  -> when we have entire s1 and (r - l) length != s1 length, shrink left pointer
    l    
     r  -> when valid == needs.size() => return true
     
     
     others return false
     
shrink left, do needs[left]++, if remove left (need[left] is 0), matched-- (not zero anymore)

*/