567. Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1's permutations is the substring of s2.

Example 1:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Constraints:

• 1 <= s1.length, s2.length <= 104
• s1 and s2 consist of lowercase English letters.

Solution:

class Solution {
    public boolean checkInclusion(String s1, String s2) {

        // Input: s1 = "ab", s2 = "eidbaooo"

        Map<Character, Integer> map = new HashMap<>();
        for (char s : s1.toCharArray()){
            map.put(s, map.getOrDefault(s, 0) + 1);
        }

        // a b 
        // eid b a ooo 
        // __. r
        //  

        int size = s1.length();

        int left = 0;
        int right = 0;
        int count = 0;
        Map<Character, Integer> windowMap = new HashMap<>();
        while(right < s2.length()){
            char cur = s2.charAt(right);
            right++;
            if (map.containsKey(cur)){
                windowMap.put(cur, windowMap.getOrDefault(cur, 0) + 1);
                count++;

                while(windowMap.get(cur) > map.get(cur)){
                    char curLeft = s2.charAt(left);
                    count--;
                    windowMap.put(curLeft, windowMap.get(curLeft) - 1);
                    left++;
                }



                if (count == size){
                    return true;
                }
            }else{
                windowMap.clear();
                left = right;
                count = 0;
            }

        }

        return false;

    }
}


// TC: O(n)
// SC: O(n)