Question

Interesting Anagram Question || OA Feb'2021 || DE SHAW || Set - 21 || 2022

Answer 1

You are given a string A. You need to solve Q queries. In each queries, you will be given a string B[i].

you need to find the count of the number of substrings of A which are anagrams of B[i].

Contraints:
1<=|A|, |B[i]|<=10^5
1<=Q<=10^5
summation|B[i]|<=2x10^5
All the strings consists of lowercase english letters.

Input1:
A: jdlidfa
B: [ "daf", "ifd", "dxzjbltsmufythgm"]

Output2:
[1, 1, 0]

Input2:
A: "lrprpqejhh"
B: [ "p", "pjeplqrr"]

Output2:
[2, 0]

This is my Approach which is partially accepted ):
#include<bits/stdc++.h>
int fun(string s,string p)
{
    int ans=0,matchsize=p.size(),l=0,r=0,n=s.size();
    if(matchsize>n)
    return ans;
    vector<int> target(26,0);
    for(char c:p)
    {
      target[c-'a']++;
    }
    while(r<n)
    {
        char c=s[r];
        if(target[c-'a']>0)
          --matchsize;
        --target[c-'a'];

        if(r-l+1==p.size())
        {
            if(matchsize==0)
            {
             ans++;
            }
            char begin_c=s[l];
            if(target[begin_c-'a']>=0)
             ++matchsize;

            ++target[begin_c-'a'];
            ++l;
        }
        ++r;
    }
    return ans;

}
vector<int> Solution::solve(string s, vector<string> &B)
{
  int n=B.size(),i;
  vector<int> ans(n,0);
  for(i=0;i<n;i++)
  {
    ans[i]=fun(s,B[i]);
  }
  return ans;
}