Header Ad

HackerEarth Mixing Strings problem solution

In this HackerEarth Mixing Strings problem solution, Heisenberg is very fond of mixing various strings together. But he has a storage problem. He wants that his strings to use as little space as possible.

He has N strings right now. He wants to store them together. To reduce space he can use this property of mixing two strings:

Suppose he has string A="abcdef" and B="cdefghi". He can mix them to form "abcdefghi".

So, two strings can be mixed if some substring at the end of A is also at the starting of B which are mixed together.

we have given the list of strings he has right now, print the minimum final characters he can get if he can mix any number of times, any of the given strings, or the intermediate strings.


HackerEarth Mixing Strings problem solution


HackerEarth Mixing Strings problem solution.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<vector>
#include<cassert>
#include<sstream>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;
#define pb push_back
#define mp make_pair
#define clr(x) x.clear()
#define sz(x) ((int)(x).size())
#define F first
#define S second
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,b) for(i=0;i<b;i++)
#define rep1(i,b) for(i=1;i<=b;i++)
#define pdn(n) printf("%d\n",n)
#define sl(n) scanf("%lld",&n)
#define sd(n) scanf("%d",&n)
#define pn printf("\n")
typedef pair<int,int> PII;
typedef vector<PII> VPII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long LL;
#define MOD 1000000007
LL mpow(LL a, LL n)
{LL ret=1;LL b=a;while(n) {if(n&1)
ret=(ret*b)%MOD;b=(b*b)%MOD;n>>=1;}
return (LL)ret;}
string mix(string a , string b)
{
int i,j,flag;
for(i=0; i<a.length(); i++)
{
flag=0;
for(j=i; j<a.length(); j++)
if((j-i)>=b.length() || b[j-i]!=a[j]){flag=1;break;}
if(flag==0)break;
}
for(j=a.length()-i; j<b.length(); j++)
a+=b[j];
return a;
}
int main()
{
int n,ar[10]={},i,j,ans=1000000,check=0;
string str[11],ret,temp;
sd(n);
for(i=0; i<n; i++)
{
cin >> str[i];
check+=str[i].size();
ar[i]=i;
}
do
{
ret=str[ar[0]];
for(i=1; i<n; i++)
ret=mix(ret,str[ar[i]]);
if(ret.length()<ans)ans=ret.length();
}while(next_permutation(ar,ar+n));
printf("%d\n",ans);
return 0;
}

Post a Comment

0 Comments