Reverse Shuffle Merge – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Reverse Shuffle Merge HackerRank Solution
#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;
}
Java Reverse Shuffle Merge HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
char[] s = ns().toCharArray();
int n = s.length;
for(int p = 0, q = n-1;p < q;p++,q--){
char d = s[p]; s[p] = s[q]; s[q] = d;
}
int[] f = new int[26];
for(int i = 0;i < n;i++){
f[s[i]-'a']++;
}
for(int i = 0;i < 26;i++){
f[i] /= 2;
}
char[] A = new char[n/2];
int ap = 0;
int[] rev = Arrays.copyOf(f, 26);
boolean[] used = new boolean[n];
int start = 0;
outer:
while(ap < n/2){
inner:
for(int i = 0;i < 26;i++){
int[] h = Arrays.copyOf(f, 26);
for(int j = start;j < n && rev[i] > 0;j++){
if(used[j])continue;
if(s[j] == 'a'+i){
A[ap++] = s[j];
rev[i]--;
used[j] = true;
start = j+1;
f = Arrays.copyOf(h, 26);
continue outer;
}else{
if(--h[s[j]-'a'] < 0){
continue inner;
}
}
}
}
}
out.println(new String(A));
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Python 3 Reverse Shuffle Merge HackerRank Solution
from collections import Counter, defaultdict
from bisect import bisect
def solve(s):
word = Counter(s)
for k, v in word.items():
word[k] = v//2
revleft = word.copy()
skipped, avail = Counter(), Counter()
locs = defaultdict(list)
for i, c in enumerate(s):
locs[c].append(i)
ans = []
live = len(s)-1
dead = len(s)
while revleft:
leftc = s[live]
avail[leftc] += 1
while avail[leftc] + skipped[leftc] > word[leftc]:
# print(live, dead, skipped, avail, revleft, locs)
cnew = min(c for c in avail.keys() if avail[c]>0 and revleft[c]>0)
ans.append(cnew)
avail[cnew] -= 1
revleft[cnew] -= 1
if revleft[cnew] == 0:
del revleft[cnew]
i = bisect(locs[cnew], dead-1) - 1
# print(i)
i = locs[cnew][i]
assert s[i] == cnew
# print(cnew, i)
for c in s[i+1: dead]:
avail[c] -= 1
skipped[c] += 1
# print(c, avail, skipped)
dead = i
assert live <= i
# print(live, ans, revleft)
live -= 1
return ''.join(ans)
print(solve(input()))
Python 2 Reverse Shuffle Merge HackerRank Solution
from bisect import bisect_left
S = raw_input()
pos = [[] for i in range(27)]
cts = [0 for i in range(27)]
for i in range(len(S)):
pos[ord(S[i])-ord('a')].append(i)
chosen = [False for i in range(len(S))]
inds = [len(pos[i])-1 for i in range(27)]
while sum(cts) < len(S)/2:
for i in range(27):
if inds[i] == -1 or cts[i] == len(pos[i])/2:
continue
good = True
for j in range(27):
if i==j or inds[j] == -1:
continue
if bisect_left(pos[j], pos[i][inds[i]], 0, inds[j]+1) + cts[j] < len(pos[j])/2:
good = False
break
if good:
chosen[pos[i][inds[i]]] = True
cts[i] += 1
for j in range(27):
if i == j or inds[j] == -1:
continue
inds[j] = bisect_left(pos[j], pos[i][inds[i]], 0, inds[j]+1) - 1
inds[i] -= 1
break
print ''.join([S[i] for i in range(len(S)) if chosen[i]])[::-1]
C Reverse Shuffle Merge HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#define MAX 10001
#define MAXBY2 5001
#define ALPHA_COUNT 26
void insert(int pos[],int position)
{
int i,j;
int num = pos[0];
for(i = 1;i <= num;i++)
{
if(pos[i] > position)
{
break;
}
}
for(j = num;j > i;j--)
{
pos[j] = pos[j - 1];
}
pos[i] = position;
pos[0]++;
return;
}
void addToFinal(char* str,char c)
{
int len = strlen(str);
str[len] = c;
str[len + 1] = '\0';
return;
}
int satisfies_property(int cum_count[][MAX],int req_count[],int column,char current)
{
int i,j;
for(i = 0;i < ALPHA_COUNT;i++)
{
if(i == current - 'a')
{
if(cum_count[i][column] < req_count[i])
{
return 0;
}
}
else
{
if(cum_count[i][column] < req_count[i])
{
return 0;
}
}
}
return 1;
}
int main() {
char str[MAX];
int count[ALPHA_COUNT][MAX];
int req_count[ALPHA_COUNT];
int cumulative_count[ALPHA_COUNT][MAX];
int length;
int i,j;
char finalstr[MAX];
finalstr[0] = '\0';
scanf("%s",str);
length = strlen(str);
for(i = 0;i < ALPHA_COUNT;i++)
{
count[i][0] = 0;
}
for(i = 0;i < length;i++)
{
insert(count[str[i] - 'a'],i);
for(j = 0;j < ALPHA_COUNT;j++)
{
if(j == str[i] - 'a')
{
if(i == 0)
{
cumulative_count[j][i] = 1;
}
else
{
cumulative_count[j][i] = cumulative_count[j][i-1] + 1;
}
}
else
{
if(i == 0)
{
cumulative_count[j][i] = 0;
}
else
{
cumulative_count[j][i] = cumulative_count[j][i-1];
}
}
}
}
for(i = 0;i < ALPHA_COUNT;i++)
{
req_count[i] = count[i][0]/2;
}
int counter = 0;
int last_index = length + 2;
int flag;
/*
for(i = 0;i < 26;i++)
{
for(j = 0;j < 5;j++)
{
printf("%d ",count[i][j]);
}
printf("\n");
}*/
//int fuck = 0;
while(counter != length/2)
{
/*fuck++;
if(fuck == 10)break;
printf("%s\n",finalstr);
for(i = 0;i < 26;i++)
{
printf("%d-",req_count[i]);
}
printf("\n");*/
for(i = 0;i < ALPHA_COUNT;i++)
{
for(j = count[i][0],flag = 0;j >= 1;j--)
{
if(count[i][j] < last_index
&& satisfies_property(cumulative_count,req_count,count[i][j],'a' + i) && req_count[i] > 0)
{
//printf("fuck = %d,i = %d,j = %d\n",fuck,i,j);
last_index = count[i][j];
addToFinal(finalstr,'a' + i);
req_count[i]--;
counter++;
flag = 1;
break;
}
}
if(flag)
{
break;
}
}
}
printf("%s",finalstr);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
