# PROBLEM LINK:

Author: Dharsan R

# DIFFICULTY:

EASY

# PREREQUISITES:

Dynamic Programming

# PROBLEM:

Given two strings S and P,you have to find the parity of the number of substrings T in S such that T and P are Twins. Two strings are said to be twins if the sum of value of the letters in the string are same. The value of a letter is their respective postion in the list of 26 alphabets

# EXPLANATION:

The naive approach to this problem is to perform brute force and consider all (N*(N-1))/2 substrings in S. Find the value of each substring and compare with the value of P,and increment the counter accordingly. This can be done in O(N^3) complexity, with some preprocessing , the same can be done in O(N^2).

An efficient way to solve this is to use Dynamic programming (DP).Let K be the value of the string P. K can be obtained in O(|P|) time complexity.Now the idea is to initialize an array A where A[i] stores the sum of values of first i letters of string S.

Declare a map or dictionary M.Now for each i such that 1<=i<=N, update the value for A[i] as 1 in dictionary M with A[i] as the key. Also make the value for 0 in dictionary M as 1 with 0 as key.

Now let us consider two valid indices i and j (1<=i<=j<=N),the value of the substring T starting from i and ending at j is A[j]-A[i-1] if i!=1,otherwise the value will be A[j].

Using the above idea, let us consider a substring T ending at position j in S.The value of string T is A[j].Suppose A[j]>=K and if M[A[j]-K] is 1, it means that there is an index i such that 1<=i<=j and A[i]=A[j]-K, therefore the substring R in S starting from i+1 and ending at j will have an value of K (i.e; R is a twin string of P). Now declare and initialize a counter C as 0 and run a loop for all 1<=j<=N, if there exists an R ending at position j satisfying the above conditions, then increment the counter C by 1.The counter variable C will give us the number of twin strings of P in S and check the parity of C.

# TIME COMPLEXITY

O(|S|+|P|)=O(N) as |S|=N and |P|<=|S|.

# SOLUTIONS:

## Setter's Solution

```
#include<bits/stdc++.h>
#include<math.h>
#include<string.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t,n,k,x;
string s,p;
cin>>t;
while(t--)
{
cin>>n;
cin>>s;
cin>>p;
map<int,int> m;
int a[n],k=0,c=0;
for(int i=0;i<p.length();i++)
k+=p[i]-96;
a[0]=s[0]-96;
if(a[0]==k)
c++;
m[a[0]]++;
m[0]++;
for(int i=1;i<n;i++)
{
a[i]=a[i-1]+(s[i]-96);
m[a[i]]++;
if(a[i]>=k)
if(m[a[i]-k]>0)
c++;
}
if(c%2==0)
cout<<"GRYFFINDOR\n";
else
cout<<"SLYTHERIN\n";
}
return 0;
}
```