567. Permutation in String

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> map = new HashMap<>();

        for (char c : s1.toCharArray()) {
            map.put(c, map.getOrDefault(c, 0)+1);
        }

        int activeCount = 0;
        int left = 0;
        for (int right = 0; right < s2.length(); right++) {
            char rightChar = s2.charAt(right);
            if (map.containsKey(rightChar)) {
                map.put(rightChar, map.getOrDefault(rightChar, 0)-1);
                if (map.get(rightChar) == 0) {
                    activeCount++;
                }
            }

            while (right - left + 1 > s1.length()) {

                char leftChar = s2.charAt(left);
                if (map.containsKey(leftChar)) {
                    if (map.get(leftChar) == 0) { // do this first! left is like a reversed operation
                        activeCount--;
                    }
                    map.put(leftChar, map.getOrDefault(leftChar, 0)+1);
                }
                left++;
            }
            // when it leaves while loop, it must right - left + 1 == s1.length()
            if (activeCount == map.size()) {
                return true;
            }
        }
        return false;
    }
}

/**
T: O(n)
S: O(n)


sliding win to find there is a win contains all chars in s1

win size == s1 size -> it's working

use a map to save s1 char, count

then run sliding win to check if cur char in this s1Map

if not in s1Map, move left;  -> this is wrong (when left - right + 1 > s1.length()), we shrimp the left

or keeps move right until we find the ans

     r
eidbaooo
    l
ab

ac = 2
    r
eidbaooo
   l
ab


ex:
when 
s1 = adc
s2 = dcda

notice to comapare this first (because 0 is the 100% accrated, 
if we minus map count first then compare != 0 later-> it might original count is not 0!!)
=> if (map.get(leftChar) == 0) {



            while (right - left + 1 > s1.length()) {

                char leftChar = s2.charAt(left);
                if (map.containsKey(leftChar)) {
                    if (map.get(leftChar) == 0) {
                        activeCount--;
                    }
                    map.put(leftChar, map.getOrDefault(leftChar, 0)+1);
                }
                left++;
            }
 */

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)

*/