Algorithm Pattern – Sliding Window

Problem

Usually if you are asked to find out substring based on one string pattern in another string, it means you have to check all possible substring in one string, so you should maintain a sliding window to check each substring candidate.

Thought

For convenience, I call two strings as pattern string and explore string.
We should go over the pattern string first and then use a hashmap to parse it.
And then we go over the explore string and use another hashmap to store the substring we meet so far.
If the length or size meets the requirement, we could consider shrinking our substring.

Algorithm Pattern

// for the pattern string
Map<Character, Integer> standard = new HashMap<>();
For(char c : str_pattern){
    Standard.put(c, standard.getOrDeafault(c, 0) + 1);
}
Int req = standard.size();

// for the explore string
Map<Character, Integer> explore = new HashMap<>();
Int found = 0;
Int left = 0, right = 0;
While(right <= str_explore.length()){
    Char cur = str_explore.charAt(right);

    put cur into explore map

    If(stand.cotainsKey(cur) && same value){
        Found++;
    }

    // shrink
    While(left <= right && size/length meet the need){
        Char remove = explore.charAt(left);

        Check if valid, if so, update result

        Remove remove from two hashmap

        Left++;
    }

    Right++;
}

return result