HackerEarth The String Monster problem solution

In this HackerEarth The String Monster problem solution As Gudi escapes the room and moves onto to the next floor, the Wizard of UD receives her at the gate!

The wizard questions her intelligence and does not allow her to move ahead unless she answers his puzzle correctly. The wizard says :

Imagine that you are trapped in a dungeon, little girl . And the gate to the exit is guarded by a Monster. The Monster eats strings. Different strings trigger different behaviors of the monster. You know the string that can make it sleep. However, you do not posses it. All you have are N strings scattered on the floor in the dungeon. You can pick up any subset of these and rearrange the characters to form the required subset. You can't pick up a partial string or discard part of any string that you pick.

Answer me, little girl, can you use these strings to form the string that shall make the monster sleep and get you out alive?

Help Gudi answer the Wizard correctly. The strings on the floor have a maximum size K , and the strings that the monster eats have a maximum size L. Each of these strings consists of only lowercase alphabets [ 'a'-'z' ].

HackerEarth The String Monster problem solution.

#include<bits/stdc++.h>


using namespace std;

#define rep(i,n) for(i=0;i<n;i++)
#define ll long long
#define elif else if
#define pii pair<int,int>
#define mp make_pair
#define pb push_back


set <string> st;
vector <string> vs;
string target;
bool Solution;

string reduce( string major, string minor)
{
  string ret;
  sort(major.begin(),major.end());
  sort(minor.begin(),minor.end());
  int i,j,n,m;
  n=major.size();
  m=minor.size();
  i=0;
  j=0;
  while(i<n && j<m)
  {
    if(major[i]==minor[j])
    {
      i++;
      j++;
      continue;
    }
    if(major[i]<minor[j]){
      ret+=major[i];
      i++;
    }
    else
      return "-1";
  }
  if(j==m)
  {
    while(i<n)
    {
      ret+=major[i];
      i++;
    }
    return ret;
  }
  return "-1";
}
void foo(int pos,string cur)
{
  if(cur.size()>target.size())
      return;
  if(pos==vs.size()/2)
  {
    sort(cur.begin(),cur.end());
    st.insert(cur);
   // cout<<cur<<endl;
    return;
  }
  foo(pos+1,cur);
  cur+=vs[pos];
  foo(pos+1,cur);
  return;
}

void boo(int pos, string cur)
{
  if(cur.size()>target.size())
      return;
  if(Solution)
    return;
  if(pos==vs.size())
  {
    sort(cur.begin(),cur.end());
    string tmp = target;
    tmp= reduce(target,cur);
    if(st.find(tmp)!=st.end())
    {
      //cout<<target<<" - "<<cur<<" = "<<tmp<<endl;
      Solution=true;
      return;
    }
    return;
  }
  boo(pos+1,cur);
  cur+=vs[pos];
  boo(pos+1,cur);
  return;
}
int main()
{

  ios_base::sync_with_stdio(0);
  int t;
  cin>>t;
  assert(1<=t && t<=100);
  while(t--)
  {
    int n,i,j,ans=0;
    st.clear();
    cin>>n;
    Solution=false;
    vs.clear();
    vs.resize(n);
    string cur;
    rep(i,n)
      cin>>vs[i];
    cin>>target;
    sort(target.begin(),target.end());
    foo(0,cur);
    cur="";
    boo(vs.size()/2,cur);
    if(Solution)
      cout<<"YES";
    else
      cout<<"NO";
    if(t>0)
      cout<<endl;
  }
 return 0;
}

Second solution

import java.io.*;
import java.util.*;

public class stringmonster {
  private static InputReader in;
  private static PrintWriter out;

  public static void main(String[] args) throws IOException {
    in = new InputReader(System.in);
    out = new PrintWriter(System.out, true);

    int t = in.nextInt();
    while(t-->0) {
      int n = in.nextInt();
      int[][] freq = new int[n][26];
      for (int i = 0; i < n; i++) {
        for (char c : in.next().toCharArray())
          freq[i][c-'a']++;
      }
      int[] goal = new int[26];
      for (char c : in.next().toCharArray())
        goal[c-'a']++;
      
      int n1 = n/2, n2 = n-n1;
      HashSet<Long> hs = new HashSet<>();
      for (int mask = 0; mask < 1 << n1; mask++) {
        int[] r = new int[26];
        for (int i = 0; i < n1; i++) {
          if (((mask>>i)&1) != 0) {
            for (int j = 0; j < 26; j++) {
              r[j] += freq[i][j];
            }
          }
        }
        boolean ok = true;
        long hss = 0;
        for (int j = 0; j < 26; j++) {
          if (r[j] > goal[j]) {
            ok = false;
            break;
          }
          r[j] = goal[j] - r[j];
          hss = hss * 2348981231L + r[j];
        }
        if (ok) {
          hs.add(hss);
        }
      }
      boolean ans = false;
      for (int mask = 0; mask < 1 << n2; mask++) {
        int[] r = new int[26];
        for (int i = 0; i < n2; i++) {
          if (((mask>>i)&1) != 0) {
            for (int j = 0; j < 26; j++) {
              r[j] += freq[i+n1][j];
            }
          }
        }
        long hss = 0;
        for (int j = 0; j < 26; j++) {
          hss = hss * 2348981231L + r[j];
        }
        ans |= hs.contains(hss);
      }
      out.println("YES");//ans?"YES":"NO");
    }
    
    out.close();
    System.exit(0);
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }
  }


}