Hashing Dashing with Sliding Window

As the name suggests, we will see hashing but before that, let's see a problem :

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

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

Output: True

Explanation: s2 contains one permutation of s1 ("ba").

Some ideas came to my mind while solving this :

How will I check whether one string is a permutation of another string?

If one string is a permutation of another string then they must one common metric. What is that?

Both strings must have the same character frequencies if one is a permutation of another. Which data structure should be used to store frequencies?

So finally we can store them in array/Maps. 

Let's make a frequency array and Map respectively:

So let's talk about the approach to solve this problem  :

Approach:  Sliding window technique along with Hashing.

Suppose the length of S1 be 'K' and length of S2 be 'N', First, Create a hash to store frequency of characters in string S1.

Now, we can traverse the string S2 for every window of size 'K' and create a hash to store the frequency of characters in that window. Now for every window, we can compare the hash of that window with the hash array of string P to check if the characters are the same or not. 

Since the characters are lower-case alphabets, we can use an array of size 26 to create the hash. Therefore, to check if two hash arrays are equal or not we will make only 26 comparisons in the worst case, which is close to O(1).

Code in C++ :

 

Let's have another problem : 

Count distinct elements in every window

Given an array A[] of size N and an integer K. Your task is to complete the function countDistinct() which prints the count of distinct numbers in all windows of size k in the array A[].

Constraints:

1 <= T <= 100

1 <= N <= K <= 10^5

1 <= A[i] <= 10^5 , for each valid i

Example:

Input:

2

7 4

1 2 1 3 4 2 3

3 2

4 1 1

Output:

3 4 4 3

2 1

Approach:  Sliding window technique along with Hashing

The trick is to use the count of the previous window while sliding the window. To do this a hash map can be used that stores elements of the current window. 

The hash-map is also operated on by simultaneous addition and removal of an element while keeping track of distinct elements. 

The problem deals with finding the count of distinct elements in a window of length k, at any step while shifting the window and discarding all the computation done in the previous step, even though k - 1 elements are same from the previous adjacent window. 

For example, assume that elements from index i to i + k - 1 are stored in a Hash Map as an element-frequency pair.

So, while updating the Hash Map in range i + 1 to i + k, reduce the frequency of the i-th element by 1 and increase the frequency of (i + k)-th element by 1.

Insertion and deletion from the HashMap takes constant time.

A dry run of the above approach:

Code in C++ :

 

Problems asked by many companies like Amazon, Microsoft, Accolite on this topic : 

Count distinct elements in every window

Permutation in String