# Reverse Shuffle Merge | HackerRank Solution [Advanced]

Problem

Given a string s such that, s ∈ merge(reverse(A), shuffle(A)) for some string A, find the lexicographically smallest A.

###### Input

A single line containing the string s.

###### Output

Find and return the string which is the lexicographically smallest valid A

###### Constraints
• 1 <= |s| ≤ 10000
• s contains only lower-case English letters, ascii[a-z]
###### Sample Input
eggegg
###### Sample Output
egg
###### Solution

Approach: Greedy Algorithm

Given S, We want to find the lexicographically smallest A such that:
S ∈ merge(reverse(A), shuffle(A))

Now this could also be written as:
S ∈ merge(reverse(A), shuffle(A))
<==>
reverse(S) ∈ merge(A, shuffle(A))

Since constraints allow us to use a O(n2) solution. We could use a brute force greedy approach.

Code Implementation

//
//  main.cpp
//  Reverse Shuffle Merge
//
//  Created by Himanshu on 23/03/22.
//

#include <iostream>
#include<vector>
#include<string>
#include<algorithm>
#include <cstring>
#define MAX_SIZE 26
using namespace std;

int main() {
string s,s1;
int n, p, ok;
int *count = new int[MAX_SIZE]();
int *passcount = new int[MAX_SIZE]();
int *acount = new int[MAX_SIZE]();
char ans[10000];

cin>>s;
n = (int) s.size();

for (int i=0; i<n; i++) {
count[s[i]-'a']++;
}

reverse (s.begin(), s.end());

for (int l=0; l<n/2; l++) {
//Checking every possible char(a-z) for position l
//in required string
for (int j=0; j<26; j++) {
if (acount[j] < count[j]/2) {
ans[l] = (char)(j + 'a');
}
acount[j]++;
p = 0;

for (int i=0; i<n; i++) {
if (ans[p] == s[i]) {
p++;
if (p > l) {
break;
}
}
passcount[s[i]-'a']++;
}

ok = 1;
for (int k=0; k<26; k++) {
//If remaining number of a particular char(a-z)
//is larger than the required number, reject the current char for
//position l
if (count[k]/2 < (passcount[k] - acount[k])) {
ok = 0;
break;
}
}

//resetting passcount for checking the number
//of types a char(a-z) is used
memset(passcount, 0, MAX_SIZE*sizeof(int));

//current char is accepted for position l
if (ok) {
break;
} else {
//rejecting the current char for position l
acount[j]--;
}
}
}

ans[n/2] = NULL;
cout<<ans<<endl;

return 0;
}


Time complexity: O(n2)