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