Sliding Window Technique Problem

what is a class and object in java

As we learn about the sliding window technique and also discuss some medium level problems, here we are going to solve some basic or you can say easy level problems.

Before going to problem, you must be aware of technique and have basic knowledge of hash map

So, here we are going to solve 2 easy problem, without wasting time come on it

Count Distinct Element in every window

Problem Statement

You have a array and a integer k, you need to find the distinct number of element in each window of size k

Input

First Integer is a test case in one line and size of the array and then the size of the window in the next line and in the third line, you have array elements

2
7 4
1 2 1 3 4 2 3
3 2
4 1 1

Output

Number of distinct elements in each window

3 4 4 3
2 1

Algorithm(sliding window technique)

A very easy question, You can see there we only need to slide the window and in every slide, we have to check the distinct number of elements.

To count the distinct number of elements you can use hashMap.

Key in hashmap represent the element and value represent the occurrence

Approach

  • Create a hash Map and insert element from array up to size k
  • In each insert check whether the element is present or not, If the element is present already you need to update the value of that element in the map to +1

  • If the element is not present you need to insert in map with value 1(value represent the occurrence) and increase dist variable value.(dist represent the distinct element)
  • Print the dist value( correspond to the first window)
  • Start from the kth index(to next window) in array and insert next element according to point 2 and point 3 and then remove the first index like this
// represent element is present and have only 1 occurence, so we decrease distinct value in our new window
        if(mp[A[i-k]] == 1) 
        {
            dist--;
        }
        mp[A[i-k]]--;       also reduce the occurence of element by 1
  • After every iteration you need to print dist variable.

You can better understand by code

// { Driver Code Starts
#include <bits/stdc++.h>
using namespace std;

void countDistinct(int[], int, int);

int main() {
    // your code goes here
    int t;
    cin >> t;
    while (t--) {

        int n, k;
        cin >> n >> k;
        int a[n];
        for (int i = 0; i < n; i++) cin >> a[i];
        countDistinct(a, k, n);
        cout << endl;
    }
    return 0;
}
// } Driver Code Ends
/*You are required to complete below method */
void countDistinct(int A[], int k, int n) {
    
    map<int,int> mp;
    int dist = 0;
    for(int i = 0;i<k;i++)
    {
        if(mp[A[i]] == 0)//element not present hence, it is distinct element
        {
            dist++;
        }
        mp[A[i]]++;// increase occurence of element i.e value in hashmap
    }
    cout<<dist<<" ";// distinct element in first window
    for(int i = k;i<n;i++)
    {
         
//removed the element from the window, if it values is 1 it means it has only 1 //occurrence and in new window, it is not present
// so we decrease dist value
        if(mp[A[i-k]] == 1) 
        {
            dist--;
        }
        mp[A[i-k]]--;
         if(mp[A[i]] == 0) // same as above
        {
            dist++;
        }
        mp[A[i]]++;
        cout<<dist<<" ";// dist element in next window
        
    }

}

Count Occurrence of Anagram

Problem

Given a word S and a text C. Return the count of the occurrences of anagrams of the word in the text.

Input

First-line contains integer T represent the test case and other 2 lines contain string’s S and C respectively

2
forxxorfxdofr
for
aabaabaa
aaba

Output

Output number of occurrence of anagram of C in S

3
4
// Explanation "for" is present in S as "for","orf","ofr"

Algorithm(sliding window technique)

This is simply a anagram problem mix with sliding window technique.

  int k = c.length()  // pane length   
   for(int i = 0;i<k;i++)   // first window slide  formation
    {
        z = z+a[i];
    }
  • Check whether string z is an anagram of C, if yes increase the count
  • Then slide the pane and remove the first window and add next window like this
for(int j = k;j<S.length();j++)
    {
        z.erase(z.begin());
        z = z+a[j];
        if(areAnagram(z,c))
        count++;
    }

Complete code is here,

#include <iostream>
using namespace std;
bool areAnagram(string str1, string str2) 
{ 
    int count1[256] = { 0 }; 
    int count2[256] = { 0 }; 
    int i; 
    for (i = 0; str1[i] && str2[i]; i++) { 
        count1[str1[i]]++; 
        count2[str2[i]]++; 
    } 
    if (str1[i] || str2[i]) 
        return false; 
    for (i = 0; i < 256; i++) 
        if (count1[i] != count2[i]) 
            return false; 
  
    return true; 
} 
int noofAna(string S,string C)
{
    int k = C.length();
    string z;
    int count = 0;
    for(int i = 0;i<k;i++)
    {
        z = z+a[i];
    }
    if(areAnagram(z,C))
    count++;
 //   cout<<z<<" ";
    for(int j = k;j<S.length();j++)
    {
        z.erase(z.begin());
        
        z = z+a[j];
    //    cout<<z<<" ";
        if(areAnagram(z,C))
        count++;
    }
    return count;
    
}
int main() {
	int t;
	cin>>t;
	while(t--)
	{
	    string S;
	    string C;
	    cin>>S;
	    cin>>C;
	    cout<<noofAna(S,C)<<endl;
	}
	return 0;
}

Hope, you learn something new.

Practice above question here by submitting your code

Tagged :

Leave a Reply

Your email address will not be published. Required fields are marked *