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.

HackerRank Problem Link

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.

//
//  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)

Leave a Reply

Your email address will not be published.