In this HackerEarth Sumit And Rohil problem solution It's a fine sunny afternoon today in California. Looking at the pleasant weather, Sumit is all ready to go out and play with his friend Rohil. Unfortunately, Rohil is down with fever. Seeing that his friend is ill, Sumit decides not to go out - instead play with Rohil inside the house. Sumit loves math, on the contrary Rohil loves strings. Sumit decides to play a game that involves more of strings and less of Maths so that Rohil could be at ease and have fun playing it.

The game is simple and is played on a piece of paper. Sumit writes down a long list of names on that paper and passes it to Rohil. Rohil gets confused on seeing so many names on that paper and asks Sumit about the game. So, Sumit explains him the rules of the game. Rohil is supposed to partition the names into groups, such that:
  • Each name belongs to exactly one group.
  • Names that belong to the same group are pairwise anagrams.
  • The first character of all the names in the same group are equal.
  • The last character of all the names in the same group are equal.
  • The number of groups is minimum possible.
Note: Two strings are called anagrams if it's possible to form one string from the other by changing the order of its characters.

Rohil would have won the game easily, if he would have been fit and fine but since he is ill right now he needs your help in winning the game. So, help out Rohil and do give him your blessings.


HackerEarth Sumit And Rohil problem solution


HackerEarth Sumit And Rohil problem solution.

#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(0);
using namespace std;
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define mp make_pair
#define all(a) a.begin(),a.end()
#define bitcnt(x) __builtin_popcountll(x)
#define MOD 10009
#define MAXN 100005
typedef unsigned long long int uint64;
typedef long long int int64;


set<string>s;
set<string>::iterator it,it1,it2;

int main(){
int i,n;
string name;
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
cin>>n;
int cnt=0;
while(cin>>name){
cnt++;
s.insert(name);
}

for(it=s.begin();it!=s.end();it++){
name=*it;
it1=it;
it1++;
string sortname=name;
sort(all(sortname));
while(it1!=s.end()){
string tmp=*it1;

if(name.length()!=tmp.length()){
it1++;
continue;
}
if(name[0]!=tmp[0]){
it1++;
continue;
}
if(name[name.length()-1]!=tmp[tmp.length()-1]){
it1++;
continue;
}
sort(all(tmp));
if(sortname==tmp){
it2=it1;
it2++;
s.erase(it1);
it1=it2;
}

}

}

cout<<s.size()<<endl;
// fclose(stdout);
return 0;
}

Second solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stdio.h>
#include <assert.h>
#include <queue>
using namespace std;

string in[111];
int n;
bool check(string a,string b){
int h=a.length();
if(h!=b.length())return false;
if(a[0] != b[0] || a[h-1]!=b[h-1])return false;

int rep[26];
for(int i=0;i<26;i++)rep[i]=0;

for(int i=0;i<h;i++){
rep[a[i]-'a']++;
rep[b[i]-'a']--;
}
for(int i=0;i<26;i++)if(rep[i]!=0)return false;
return true;

}

int sol;
int main(){
cin>>n;
assert(1<=n && n<=100);
sol=n;
for(int i=0;i<n;i++){
cin>>in[i];
assert(1<=in[i].length() && in[i].length()<=100);
for(int j=0;j<in[i].length();j++){
assert('a'<=in[i][j] && in[i][j]<='z');
}
for(int j=0;j<i;j++){
if(check(in[i],in[j])){
sol--;
break;
}
}
}
string g;
if(cin>>g)
assert(false);
cout<<sol<<endl;
}