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