0 like 0 dislike
958 views
| 958 views

0 like 0 dislike
An array of numbers and favourite numbers are given. we have to find the number of sub arrays which includes all the favourite numbers atleast once.

Constraints:
Let size of NUMBERS array be N, and size of favourite numbers be K
1 <=N <= 10^6
1<=K<=N

EXAMPLE:
NUMBERS :{1,2,1,1,1,1}
Favourite Numbers: {1,1,2}

Explanation:
(1,2,1) , (1,2,1,1), (1,2,1,1,1), (1,2,1,1,1,1), (2,1,1), (2,1,1,1), (2,1,1,1,1)

NUMBERS: 3 9 6 9 2 2 4
FAVOURITE NUMBERS: 4 9

4
(3,9,6,9,2,2,4), (9,6,9,2,2,4) ,(6,9,2,2,4) , (9,2,2,4)

Any help would be highly appreciated.Sorry! I couldn't recall the every detail of the question
by Expert (30,360 points)
0 like 0 dislike

A similar problem like this is https://leetcode.com/problems/number-of-substrings-containing-all-three-characters/. In your case u can keep track of fav elements in hashmap and do the job as shown:
Here is simple solution for the problem I mentioned : class Solution {
public:
int numberOfSubstrings(string s) {

``````    int a=0,b=0,c=0;
int i=0;
int j=0;
int ans=0;
int n=s.size();
for(int i=0;i<s.size();++i)
{
if(a>0 && b>0 && c>0)
{
ans+=n-j+1;

if(s[i]=='a') a--;
if(s[i]=='b') b--;
if(s[i]=='c') c--;
continue;
}
if(j==s.size()) break;

while(j<s.size() && (a<=0 || b<=0 || c<=0))
{
if(s[j]=='a') a++;
if(s[j]=='b') b++;
if(s[j]=='c') c++;

j++;
}
if(a>0 && b>0 && c>0) ans+=n-j+1;

if(s[i]=='a') a--;
if(s[i]=='b') b--;
if(s[i]=='c') c--;
}
return ans;
}
``````

};

by Expert (30,360 points)