In this HackerEarth Substring Queries problem solution, we have given a string S, answer Q queries. Each query contains string qstr. Please output the number of substrings of S that contain some anagram of qstr as a subsequence.

## HackerEarth Substring Queries problem solution.

```#include <bits/stdc++.h>
using namespace std;

#define MOD                     1000000007
#define pb(x)                   push_back(x)
#define mp(x,y)                 make_pair(x,y)
#define FF                      first
#define SS                      second
#define s(n)                    scanf("%d",&n)
#define sl(n)                   scanf("%lld",&n)
#define sf(n)                   scanf("%lf",&n)
#define ss(n)                   scanf("%s",n)
#define sc(n)                   {char temp[4]; ss(temp); n=temp[0];}
#define INF                     (int)1e9
#define LINF                    (long long)1e18
#define EPS                     1e-9
#define maX(a,b)                ((a)>(b)?(a):(b))
#define miN(a,b)                ((a)<(b)?(a):(b))
#define abS(x)                  ((x)<0?-(x):(x))

typedef long long ll;
typedef unsigned long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<int,PII> TRI;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<ll> vl;
typedef vector<PII> VII;
typedef vector<TRI> VT;

int n;
int TEST_NO;
char a[100005];
int cnt[62];
ll ONE = 1;

inline int val(char c) {
if(c >= 'a') return 10 + 26 + c - 'a';
if(c >= 'A') return 10 + c - 'A';
else return c - '0';
}

void precompute() {

}
ss(a);
n = strlen(a);
}
void preprocess() {

}

int st = 0, en = 0;
ll run = 0;
ll ans = 0;
memset(cnt, 0, sizeof cnt);
while(en < n and st < n) {
ans += n - en;
int sub = val(a[st]);
cnt[sub]--;
if(cnt[sub] == 0) run ^= ONE << sub;
st++;
}
en++;
}
return ans;
}

void solve() {
int q;
s(q);
while(q--) {
string qstr;
cin >> qstr;
int len = qstr.length();
for (int i = 0; i < len; ++i) {
}
}
}

int main() {
precompute();
int t;
s(t);
for(TEST_NO = 1; TEST_NO <= t; TEST_NO ++) {
preprocess();
solve();
}
return 0;
}```

### Second solution

```#include<bits/stdc++.h>

using namespace std;

#define vi vector < int >
#define pii pair < int , int >
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define foreach(it,v) for( __typeof((v).begin())it = (v).begin() ; it != (v).end() ; it++ )
#define ll long long
#define llu unsigned long long
#define MOD 1000000007
#define INF 2000000000
#define dbg(x) { cout<< #x << ": " << (x) << endl; }
#define dbg2(x,y) { cout<< #x << ": " << (x) << " , " << #y << ": " << (y) << endl; }
#define all(x) x.begin(),x.end()
#define mset(x, v) memset(x, v, sizeof(x))
#define si(x) (int)x.size()

int ID(char ch)
{
if('a' <= ch && ch <= 'z')
return ch - 'a';
if('A' <= ch && ch <= 'Z')
return ch - 'A' + 26;
if('0' <= ch && ch <= '9')
return ch - '0' + 52;
assert(0);
}

ll solve(string s,string q)
{
int i,j,n = si(s),m = si(q);
int pos[62],f[62];
for(i=0;i<62;i++)
{
pos[i] = -1;
f[i] = 0;
}
vi v;
for(i=0;i<m;i++)
{
f[ID(q[i])] = 1;
v.pb(ID(q[i]));
}
ll ans = 0;
int mx = -1,mid = -1;
int done = 0;
for(i=n-1;i>=0;i--)
{
int id = ID(s[i]);
if(pos[id] == -1 && f[id])
done++;
if(f[id])
{
pos[id] = i;
mx = max(mx,i);
if(i == mx)
mid = id;
if(id == mid)
{
mx = -1;
for(j=0;j<si(v);j++)
{
int p = v[j];
mx = max(mx,pos[p]);
if(mx == pos[p])
mid = p;
}
}
}
if(done != m)
{
continue;
}
ans += (n-mx);
}
return ans;
}

int main()
{
int t,n,i,q;
scanf("%d",&t);
assert(1 <= t && t <= 3);
while(t--)
{
string s;
cin>>s;
n = si(s);
assert(1 <= n && n <= 100000);
scanf("%d",&q);
assert(1 <= q && q <= 200);
while(q--)
{
string qs;
cin>>qs;
int m = si(qs);
assert(1 <= m && m <= 62);
ll ans = solve(s,qs);
printf("%lld\n",ans);
}
}
return 0;
}```