In this HackerEarth Smallest chosen word problem solution You are given three strings s1, s2, and s3. Let x be any subsequence of s2 (x can be an empty string). The name is in the form of (s1 + x + s3), here (+) means concatenation of strings. You are required to print the lexicographically-smallest string s.

Note: The string contains only lowercase letters.


HackerEarth Smallest chosen word problem solution


HackerEarth Smallest chosen word problem solution.

#include <bits/stdc++.h>
using namespace std;

void boost()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}

bool comp(pair<char,int> &a,pair<char,int> &b)
{
if(a.first==b.first)
return a.second<b.second;
return a.first<b.first;
}

int main()
{
boost();
string s1,s2,s3;
int len1,len,i,fl=0,len2;
cin>>len1>>len>>len2;
cin>>s1>>s2>>s3;
string x;
for(i=0;i<len2;i++)
{
if(s3[i]!=s3[0])
{
if(s3[i]>s3[0])
fl=1;
break;
}
}

vector< pair < char, int> > vp;
for(i=0;i<len;i++)
vp.push_back(make_pair(s2[i],i));
sort(vp.begin(),vp.end(),comp);
char c=s3[0];
int ind=-1;
for(i=0;i<len;i++)
{

if(ind>vp[i].second)
continue;
if(vp[i].first==c && !fl)
break;
if(vp[i].first>c)
break;
x.push_back(vp[i].first);
ind=vp[i].second;
}
cout<<s1+x+s3<<endl;
}

Second solution

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int maxn = 2e5 + 17;
string s1, s2, s3;
int main(){
ios::sync_with_stdio(0), cin.tie(0);
cin >> s1 >> s2 >> s3 >> s1 >> s2 >> s3;
string ans = s3;
reverse(s2.begin(), s2.end());
for(auto c : s2)
ans = min(ans, c + ans);
cout << s1 + ans << '\n';
}