Reverse Shuffle Merge - Hacker Rank Solution

Given a string, , we define some operations on the string as follows:

a.  denotes the string obtained by reversing string . Example: 

b.  denotes any string that's a permutation of string . Example:

c.  denotes any string that's obtained by interspersing the two strings  & , maintaining the order of characters in both. For example,  & , one possible result of  could be , another could be , another could be  and so on.

Given a string  such that  for some string , find the lexicographically smallest .

For example, . We can split it into two strings of . The reverse is  and we need to find a string to shuffle in to get . The middle two characters match our reverse string, leaving the  and  at the ends. Our shuffle string needs to be . Lexicographically , so our answer is .

Function Description

Complete the reverseShuffleMerge function in the editor below. It must return the lexicographically smallest string fitting the criteria.

reverseShuffleMerge has the following parameter(s):

• s: a string

Input Format

A single line containing the string .

Constraints

•  contains only lower-case English letters, ascii[a-z]

Output Format

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

Sample Input 0

eggegg

Sample Output 0

egg

Explanation 0

Split "eggegg" into strings of like character counts: "egg", "egg"
reverse("egg") = "gge"
shuffle("egg") can be "egg"
"eggegg" belongs to the merge of ("gge", "egg")

The merge is: gge.

'egg' < 'gge'

Sample Input 1

abcdefgabcdefg

Sample Output 1

agfedcb

Explanation 1

Split the string into two strings with like characters:  and .
Reverse  = 
Shuffle  can be 
Merge to bcdefga

Sample Input 2

aeiouuoiea

Sample Output 2

eaid

Explanation 2

Split the string into groups of like characters: 
Reverse  = 
These merge to uoiea

Reverse Shuffle Merge - Hacker Rank Solution

Given S, We want to find the lexicographically smallest A such that:

S ∈ merge(reverse(A), shuffle(A))

Observation 1:

S ∈ merge(reverse(A), shuffle(A))
<==>
reverse(S) ∈ merge(A, shuffle(A))

We know the length of A must be half the length of S. It must also contain half the number of each character as well. So we just need to find a smallest A with given number of 'a', given number of 'b', etc.

For example, if S = "aegeaggg", (2 'a', 2 'e', 4 'g'), we know A has (1 'a', 1 'e', 2 'g') exists.

S' = reverse(S) = "gggaegea"

We can calculate the answer one by one:

Given that S' starts with three 'g' characters and there are only two in A, we can start with 'gg' and 'g' as our two strings. Test to see if we can add 'a' to 'g' and make 'ggga'. We can, so now our A = 'gg' and A[shuffle] = 'ga'. Remaining letters are 'ea' and for shuffle, 'eg'. Since 'e' < 'g', analyze that first. A = 'gg', A[shuffle] = 'gae' can merge to 'gggae'. Now try the 'g' and get merge = 'ggggaeg' and we've used all the shuffle letters. Add in the A letters in order 'ea' and we've got A = 'ggea' and A[shuffle] = 'gaeg'. 'gaeg' < 'ggea'

Another explanation

Assume that A starts with 'a'. We need to think if there is any valid string which begins with "a". Basically, is there any substring that consists of (1 'e', 2 'g') and start with "a"? If start with "a", we can never get 2 'g', so A cannot start with 'a'. Similarly, if we try 'e', that turns out to be invalid too. So A must start with 'g'. Next, we need to try if A can start with "ga", the first "ga" can be found in S'[0...3], so we just need to know if there are (1 'e', 1 'g') in S'[4...7]. So A can start with "ga". Carry on this way till we arrive at the answer: "gaeg"

Question:
If we need to find if there are any possible values of A which have some given prefix, why we just need to find the smallest position that contains that prefix?
If this position is smaller, in the substring after this position, it is more likely that we will find the given number of remaining letters, so we can greedily use the smallest position.

Problem Setter's code:

C++

#include<map>
#include<set>
#include<ctime>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<vector>
#include<cstdio>
#include<string>
#include<cassert>
#include<cstring>
#include<numeric>
#include<sstream>
#include<iterator>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define MM(a,x) memset(a, x, sizeof(a))
#define P(x) cout<<#x<<" = "<<x<<endl;
#define P2(x,y) cout<<#x<<" = "<<x<<", "<<#y<<" = "<<y<<endl;
#define PV(a,n) for(int i=0;i<n;i++) cout<<#a<<"[" << i <<"] = "<<a[i]<<endl;
#define TM(a,b) cout<<#a<<"->"<<#b<<": "<<1.*(b-a)/CLOCKS_PER_SEC<<"s\n";

string S;
int d[10010];
int n;
int c[26], w[26];

int main() {
    cin >> S;
    reverse(S.begin(), S.end());
    n = S.length();
    assert(n <= 10000);
    for(int i = 0; i < n; i++) d[i] = S[i] - 'a';
    for(int i = 0; i < n; i++) c[d[i]]++;
    for(int i = 0; i < 26; i++) assert(c[i] % 2 == 0);
    for(int i = 0; i < 26; i++) w[i] = c[i] / 2;
    vector<int> ret(n / 2);
    for(int i = 0; 2 * i < n; i++) {
        for(int c = 0; c < 26; c++) {
            ret[i] = c;
            int p = 0;
            int l = 0;
            for(int j = 0; j < n; j++) {
                if(ret[p] == d[j]) {
                    p++;
                    l = j;
                    if(p > i) break;
                }
            }
            if(p <= i) continue;
            int want[26] = {};
            for(int j = 0; j < 26; j++) want[j] = w[j];
            for(int j = 0; j <= i; j++) want[ret[j]]--;
            int have[26] = {};
            for(int j = l + 1; j < n; j++) have[d[j]]++;
            int ok = 1;
            for(int j = 0; j < 26; j++) if(want[j] < 0 || want[j] > have[j]) ok = 0;
            if(ok) break;
        }
    }
    string r;
    for(int i = 0; 2 * i < n; i++) r += char(ret[i] + 'a');
    cout << r << endl;
    return 0;
}