As we learn about the sliding window technique and also discuss some medium level problems, here we are going to solve Count Distinct elements in Every Window .

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

Table of Contents

*Count Distinct Elements in every window*

*Count Distinct Elements 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*

*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.

- Make a pane of size
**C.length()**and slide it to all window in**S**(Learn pane and window technique here) - Create a string of size C.length() from
**S**like this

```
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;
}
```

I Hope, you learn Count Distinct elements in Every Window.

Practice above question here by submitting your code