HackerRank Reverse Shuffle Merge solution

YASH PAL,

In this HackerRank Reverse Shuffle Merge interview preparation kit problem solution, given a string s such that s E merge(reverse(A), shuffle(A)) for some string A, find the lexicographically smallest A.

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 s.

HackerRank Reverse Shuffle Merge Interview preparation kit solution

HackerRank Reverse Shuffle Merge solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys
from collections import Counter

# Complete the reverseShuffleMerge function below.
def reverseShuffleMerge(s):
    s = list(reversed(s))
    remaining_dict,required_dict,added_dict = {},{},{}
    for c in s:
        if c not in remaining_dict:
            remaining_dict[c]=1
        else:
            remaining_dict[c]+=1
    for key,value in remaining_dict.items():
        required_dict[key] = value // 2
        added_dict[key] = 0
    char_list=[]
    index = 0
    min_index = 0
    min_char = '|'
    while index < len(s):
        char = s[index]
        if required_dict[char]>added_dict[char]:
            if char < min_char:
                min_char = char
                min_index = index
            if remaining_dict[char]-1<required_dict[char]-added_dict[char]:
                while index>min_index:
                    index-=1
                    char = s[index]
                    remaining_dict[char]+=1
                added_dict[char]+=1
                char_list.append(char)
                min_char = '|'
        remaining_dict[char]-=1
        index+=1
    return "".join(char_list)

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = input()

    result = reverseShuffleMerge(s)

    fptr.write(result + 'n')

    fptr.close()

Reverse Shuffle Merge solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
	static public class CharData {
		int total;
		int skipped;
		int taken;
		boolean hasToTake(){
			return 2*skipped == total;
		}
		boolean hasToSkip(){
			return 2*taken == total;
		}
		void putBack(){
			taken--;
			skipped++;
		}
	}  

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		String s = new StringBuilder(in.nextLine()).reverse().toString();
		CharData cd[] = new CharData['z' - 'a' + 1];
		for(int i=0;i<cd.length;i++){
			cd[i]=new CharData();
		}
		for (int i = 0; i < s.length(); i++) {
			cd[s.charAt(i)-'a'].total++;
		}
		char [] r = new char[s.length()/2];
		int ri=0;
		for (int i = 0; i < s.length(); i++) {
			char ch = s.charAt(i);
			CharData di = cd[ch-'a'];
			if(di.hasToSkip()){
				di.skipped++;
			}else {
				while(ri>0 && r[ri-1]>ch && !cd[r[ri-1]-'a'].hasToTake()){
					cd[r[--ri]-'a'].putBack();
				}
				r[ri++]=ch;
				di.taken++;
			}
		}
		System.out.println(new String(r));
		in.close();
	}
}

Problem solution in C++ programming.

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

char in[10005];
int L[128];
int need[128];
char ans[10005];
int ansPos;

using namespace std;

int main()
{
	scanf("%s", in);
    for(int i=0; in[i]; ++i){
        ++L[in[i]];
    }
    int len=strlen(in);
    for(int j=0; j < 128; ++j)
        need[j]=L[j]/2;
    int pos=len-1;
    while(ansPos < len/2){
        bool init=0;
        char best;
        int ind, i;
        for(i=pos; i >= 0; --i){
            if((!init || in[i] < best) && need[in[i]]){
                init=1;
                best=in[i];
                ind=i;
            }
            L[in[i]]--;
            if(L[in[i]] < need[in[i]])
                break;
        }
        for(; i < ind; ++i){
            ++L[in[i]];
        }
        --need[best];
        ans[ansPos++]=best;
		pos=ind-1;
    }
    printf("%s", ans);
	return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void reverse(char* s,char *rev,int len){
    int i=len-1,j=0;
    while(i>=0){
        rev[j++] = s[i];
        i--;
    }
    rev[j] = '';
}

int find_occ(char *s, char match, int beg, int end){
    int i;
    for(i=beg;i<=end;i++){
        if(s[i]==match){
            return i;
        }
    }
    return -1;
}

int next_min(int arr[], int n, int count){
    int i;
    for(i=0;i<n;i++){
        if(arr[i]>0 && count==0){
            return i;
        }
        else if(arr[i]>0){
            count--;
        }
    }
    return -1;
}

int subseq(char *s, int freq[], int beg, int end){
    int i;
    for(i=beg;i<=end;i++){
        freq[s[i]-97]--;
    }
    for(i=0;i<26;i++){
        if(freq[i]>0){
            return 0;
        }
    }
    return 1;
}

int main() {

    char s[10001],rev[10001],a[10001];
    scanf("%s",s);
    int i,len = strlen(s), freq[26];
    reverse(s,rev,len);
    for(i=0;i<len;i++){
        freq[s[i]-97]++;    
    }
    for(i=0;i<26;i++){
        freq[i] /=2;
    }
    int beg = 0,counter =0,next=0;
    while(counter<len/2){
        char candidate_char = next_min(freq,26,next)+97;
        int pos = find_occ(rev,candidate_char,beg,len-1);
        // copy freq_arr
        int freq_copy[26];
        for(i=0;i<26;i++){
            freq_copy[i] = freq[i];
        }
        freq_copy[candidate_char-97]--;
        int satisfy = subseq(rev,freq_copy,pos+1,len-1);
        if(satisfy){
            a[counter++] = candidate_char;
            freq[candidate_char-97]--;
            next = 0;
            beg = pos+1;
//            printf("str is");
//            int k;
//            for(k=0;k<counter;k++)
//            {printf("%c",a[k]);
//            }
//            printf("n");
        }
        else{
            next++;
        }
    }
    a[counter] = '';
    printf("%s",a);
    return 0;
}

Problem solution in JavaScript programming.

function getPos(a, v, c) {
    var p={}, i, max=-1;
    for ( var k in c ) { 
        for ( i=0; i<a.length; ++i ) {
            if ( a[i]==k && v[i]==c[k] ) {
                if ( max<(p[k]=i) ) max=i; 
                break;
            }
        }
    }
    return {max:max, pos:p};
}

function smallest(a, i, end, c) {
    var min = 'z', pos=-1;
    for (;i<end;++i) { 
        if ( c[a[i]]==null ) continue;
        if ( min>=a[i]) min=a[pos=i]; 
    }
    return {elm:min, pos:pos};
}

function processData(input) {
    var a = input.split(''), i, j, n=a.length, cD={}, c={}, v=[], p, r=[];
    for ( i=0; i<n; ++i ) {
        if ( cD[a[i]]==null ) v.push(cD[a[i]] = 1); else v.push(++cD[a[i]]);
    }
    for ( var k in cD ) { c[k] = cD[k]/2; }
    //console.log(input);
    var end = a.length;
    p = getPos(a, v, c);
    //console.log( 'v',v, 'c',c, 'p',p, 'r',r);
    for ( i=p.max; i>=0; ) {
        var s = smallest(a, i, end, c);
        //console.log( 'i',i, 'end',end, 's',s);
        r.unshift(s.elm);
        if ( c[s.elm]<=1 ) delete c[s.elm]; else --c[s.elm];
        end = s.pos;
        p = getPos(a, v, c);
        i = p.max;
        //console.log( 'v',v, 'i',i, 'c',c, 'p',p, 'r',r);
        if ( p.max == -1 ) break;
    }
    console.log(r.reverse().join(''));
}  

process.stdin.resume();
process.stdin.setEncoding("ascii");
_input = "";
process.stdin.on("data", function (input) {
    _input += input;
});

process.stdin.on("end", function () {
   processData(_input);
});

coding problems solutions Hackerrank Problems Solutions interview prepration kit