Given a set of characters S and an input string STR, problem is to find the smallest window in STR which will contain all the characters in S. Both, S and STR can have repeated occurrences of a given character.
Approach:
The algorithm follows a sliding window approach. We maintain two hash maps, toFind and hasFound, both of whose sizes are 256 (maximum number of characters possible).
Value in toFind denotes the number of occurrences of that character in S.
There is a variable cnt, which is initialized to 0. This denotes the number of characters in S that have been found so far in STR.
Iterate through the length of STR.
For each character found, increase by 1 the value of hasFound of that character. If the character has a hasFound value still less than its toFind value, increase the cnt by 1.
If the value of cnt equals the size of S, or in other words, all characters of S are found in STR, we try to slide the window towards the right. This is done by removing the leftmost characters which are not in S, or which have a hasFound value greater that toFind value.
If after removing the unwanted characters, the window length becomes smaller than previously found window length, update it. (Initialize the window length to INT_MAX)
Approach:
The algorithm follows a sliding window approach. We maintain two hash maps, toFind and hasFound, both of whose sizes are 256 (maximum number of characters possible).
Value in toFind denotes the number of occurrences of that character in S.
There is a variable cnt, which is initialized to 0. This denotes the number of characters in S that have been found so far in STR.
Iterate through the length of STR.
For each character found, increase by 1 the value of hasFound of that character. If the character has a hasFound value still less than its toFind value, increase the cnt by 1.
If the value of cnt equals the size of S, or in other words, all characters of S are found in STR, we try to slide the window towards the right. This is done by removing the leftmost characters which are not in S, or which have a hasFound value greater that toFind value.
If after removing the unwanted characters, the window length becomes smaller than previously found window length, update it. (Initialize the window length to INT_MAX)
Read full article from Find the minimum window in a string containing all characters of another string | CODING INTERVIEW ARCHIVES
No comments:
Post a Comment