HackerRank Reverse Shuffle Merge solution

In this HackerRank Reverse shuffle merge interview preparation kit problem, You need to complete the reverseShuffleMerge function.

Problem solution in Python programming.

#!/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()

Problem solution in Java Programming.

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);
});