Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerEarth The String Monster problem solution

YASH PAL, 31 July 2024
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

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());
}
}


}
coding problems

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes