In this post, we will solve HackerRank Reverse Shuffle Merge Problem Solution. Given a string, A, we define some operations on the string as follows:
a. reverse(A) denotes the string obtained by reversing string A. Example: reverse(“abc”) = “cba”
b. shuffle(4) denotes any string that’s a permutation of string A. Example: shuffle (“god”) [‘god’, ‘gdo’, ‘ogd’, ‘odg’, ‘dgo’, ‘dog’]
c. merge(A1, A2) denotes any string that’s obtained by interspersing the two strings Al & A2, maintaining the order of characters in both. For example, A1 = “abc” & A2 = “def”, one possible result of merge(A1, A2) could be “abcdef”, another could be “abdecf”, another could be “adbecf” and so on.
Given a string s such that s merge (reverse (A), shuffle (A)) for some string A. find the lexicographically smallest A.
For example, s = abab. We can split it into two strings of ab. The reverse is ba and we need to find a string to shuffle in to get abab. The middle two characters match our reverse string, leaving the a and b at the ends. Our shuffle string needs to be ab. Lexicographically ab < ba so our answer is ab.
unction 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.
Output Format
Find and return the string which is the lexicographically smallest valid .
Sample Input 0
eggegg
Sample Output 0
egg
Explanation 0
Split “eggegg” into strings of like character counts: “egg”, “egg”
reverse(“egg”) = “gge”
shuffle(“egg”) can be “egg”
“eggegg” belongs to the merge of (“gge”, “egg”)
The merge is: eggegg.
‘egg’ < ‘gge’
Sample Input 1
abcdefgabcdefg
Sample Output 1
agfedcb
Reverse Shuffle Merge C Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <strings.h>
#include <stdbool.h>
#if 0
#define PRINT(_str...) printf(_str)
#else
#define PRINT(_str...)
#endif
char arr[10001];
char output[10001];
bool isSmallest(int *freq, int idx, bool main) {
if (!freq[idx]) {
printf("No instances of %c left in %s\n",
idx + 'a', main ? "freq" : "temp");
printf("%s", output);
exit(-1);
}
for (int i = idx - 1; i >=0; i--) {
if (freq[i]) {
return false;
}
}
return true;
}
#define PRINT_CHAR(char) do { \
output[offset] = char; \
offset++; \
needed[char - 'a']--; \
} while (0)
int main() {
int freq[26];
bzero(freq, sizeof(freq));
bzero(output, sizeof(output));
scanf("%s", arr);
int len = 0;
for (int i = 0; arr[i]; i++, len++) {
freq[arr[i] - 'a']++;
}
for (int i = 0; i < 26; i++) {
if (freq[i] % 2) {
printf("ERROR - odd count (%d) of %c\n",
freq[i], i + 'a');
return -1;
}
freq[i] /= 2;
}
int needed[26];
int skipped[26];
int temp[26];
bzero(temp, sizeof(temp));
bzero(skipped, sizeof(skipped));
bcopy(freq, needed, sizeof(freq));
int offset = 0;
int last_print = len;
for (int i = len - 1; i >= 0; i--) {
char cur = arr[i];
int idx = cur - 'a';
PRINT("Checking idx %d - %c\n", i, arr[i]);
if (needed[idx] == 0) {
PRINT(" Not needed\n");
continue;
}
if (isSmallest(needed, idx, true)) {
PRINT(" Adding\n");
PRINT_CHAR(cur);
last_print = i;
for (int j = 0; j < 26; j++) {
skipped[j] += temp[j];
temp[j] = 0;
}
continue;
}
temp[idx]++;
if ((skipped[idx] + temp[idx]) <= freq[idx]) {
PRINT(" Skipping\n");
continue;
}
PRINT(" Hit skip limit\n");
bool added = false;
for (int j = last_print - 1; j >= i; j--) {
char tempchar = arr[j];
int tempidx = tempchar - 'a';
PRINT(" Reconsidering index %d - %c\n", j, arr[j]);
if (needed[tempidx] == 0) {
PRINT(" Not needed\n");
} else if ((tempchar <= cur) && isSmallest(temp, tempidx, false)) {
PRINT(" Adding\n");
PRINT_CHAR(tempchar);
temp[tempidx]--;
last_print = j;
added = true;
if (tempchar == cur) {
i = j;
bzero(temp, sizeof(temp));
break;
}
} else {
PRINT(" Skipping\n");
skipped[tempidx]++;
temp[tempidx]--;
}
}
for (int j = 0; j < 26; j++) {
if (temp[j]) {
printf("TEMP NOT RESET PROPERLY - %d=%d\n", j, temp[j]);
return -1;
}
}
if (!added) {
PRINT(" Nothing added yet. Printing last found\n");
PRINT_CHAR(cur);
last_print = i;
}
}
if (offset != len / 2) {
printf("BAD FINAL OFFSET (%d, %d)\n", offset, len);
return -1;
}
printf("%s\n", output);
return 0;
}Reverse Shuffle Merge C++ Solution
#include <cmath>
#include <cstdio>
#include <array>
#include <vector>
#include <iterator>
#include <iostream>
#include <algorithm>
template <bool DEBUG = false>
class State {
public:
typedef std::array<size_t, 26> Counts;
typedef std::vector<size_t> Needs;
State(const std::string& str, const std::string& expect = "")
: source_(str), expect_(expect),
count_(CountChars(str)),
need_(Constrain(str, count_)),
written_({0}), out_() {
out_.reserve(source_.size() / 2);
}
void PrintState(auto ch, auto end) const {
for (auto st = need_.cbegin(); ch != end; ++st, ++ch) {
std::cout << *ch;
if (*st != 0) std::cout << ": " << *st;
std::cout << std::endl;
}
}
const std::string& Solve() {
if (!out_.empty()) return out_;
auto begin = source_.crbegin();
auto end = source_.crend();
for (auto guard = begin; guard != end; ++guard) {
// find first non-zero constraint
size_t ix = std::distance(source_.crbegin(), guard);
if (need(ix) <= written(*guard)) {
continue;
}
// write characters, preferring lower values
begin = Write(begin, guard + 1, *guard);
if (DEBUG && out_ > expect_) {
PrintState(source_.crbegin(), guard + 1);
return out_;
}
}
for (auto ch = begin; ch != end; ++ch) {
if (written((*ch)) < count(*ch)) {
out_.push_back(*ch);
++written(*ch);
}
}
if (DEBUG && out_.size() != source_.size() / 2) {
PrintState(source_.crbegin(), source_.crend());
}
return out_;
}
private:
static Counts CountChars(const std::string& str) {
Counts count = {0};
for (auto ch = str.cbegin(); ch != str.cend(); ++ch) {
++count[*ch - 'a'];
}
for (auto it = count.begin(); it != count.cend(); ++it) {
*it /= 2;
}
return count;
}
static Needs Constrain(const std::string& str, Counts take) {
std::vector<size_t> need(str.size());
auto st = need.rbegin();
for (auto ch = str.cbegin(); ch != str.cend(); ++ch, ++st) {
auto& c = take[*ch - 'a'];
*st = c; if (c != 0) --c;
}
return need;
}
auto Write(auto begin, auto end, char limit = 'z') {
for (; begin != end; ++begin) {
char low = limit + 1;
for (auto ch = begin; ch != end; ++ch) {
if (*ch < low && written(*ch) < count(*ch)) {
low = *ch;
begin = ch;
}
}
if (low == limit + 1) return end;
out_.push_back(*begin);
++written(*begin);
if (DEBUG && out_ > expect_) return end;
if (low == limit) return begin + 1;
}
return begin;
}
size_t count(char ch) const {
return count_[ch - 'a'];
}
size_t need(size_t ix) const {
return need_[ix];
}
size_t written(char ch) const {
return written_[ch - 'a'];
}
size_t& written(char ch) {
return written_[ch - 'a'];
}
const std::string& source_;
const std::string& expect_;
const Counts count_;
const Needs need_;
Counts written_;
std::string out_;
};
int main() {
std::string str;
std::cin >> str;
static const bool debug = false;
std::string expect;
if (debug) std::cin >> expect;
State<debug> state(str, expect);
std::string out = state.Solve();
std::cout << out << std::endl;
return 0;
}Reverse Shuffle Merge C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
class Solution {
public static void GetLexicographicallySmallestStr(string str){
int[] charFrequence ;
charFrequence=GetCharFrequence(str);
}
static void GetString(int []charFrequence,char[] sortStr, string str){
StringBuilder strB=new StringBuilder();
int strIndex=0;
int printedIndex=0;
str= stringReverseString1(str);
for(int index=0;index<sortStr.Length;index++){
for(;strIndex<str.Length;strIndex++){
if(charFrequence[sortStr[index]-97]==0){
break;
}
//Console.WriteLine(sortStr[index]+"<"+str[strIndex]);
if(sortStr[index]<str[strIndex]){
//Console.WriteLine(GetFrq(str.Substring(strIndex),str[strIndex])+"<="+charFrequence[str[strIndex]-97]+"frq"+ str[strIndex]);
if(GetFrq(str.Substring(strIndex),str[strIndex])<=charFrequence[str[strIndex]-97]){
//Console.Write(" charAt["+strIndex+"]="+str[strIndex]+"befr ||");
strIndex=checkPreviousCharsFrq(charFrequence,sortStr,index+1,strIndex,str,printedIndex+1);
//Console.Write(" ch["+strIndex+"]="+str[strIndex]+" aftr PrChar() ||");
if(charFrequence[str[strIndex]-97]!=0){
strB.Append(str[strIndex]);
printedIndex=strIndex;
charFrequence[str[strIndex]-97]--;
// Console.Write("o/p"+strB);
}
}
}else if(sortStr[index]==str[strIndex]){
if(charFrequence[str[strIndex]-97]!=0){
strB.Append(str[strIndex]);
printedIndex=strIndex;
charFrequence[str[strIndex]-97]--;
//Console.Write("o/p"+strB);
}
}
}
}
Console.WriteLine(strB);
}
public static int checkPreviousCharsFrq(int[] charFrequence,char[] sortStr,int index,int charIndex,string str, int strIndex){
char toBePrinted;
char ch=str[charIndex];
int tempIndex=strIndex;
//Console.WriteLine("ch["+charIndex+"]="+ch+" in PrChar() ||");
for(;index<sortStr.Length ;index++){
//Console.WriteLine(" sortStr["+tempIndex+"]="+sortStr[index]+"<="+ch+" chin");
if((sortStr[index])<=ch){
if(charFrequence[sortStr[index]-97]!=0){
toBePrinted=sortStr[index];
for(tempIndex=strIndex;(tempIndex<charIndex);tempIndex++){
//Console.WriteLine(str[tempIndex]+"--"+tempIndex+"=="+toBePrinted+" at:"+index);
if(str[tempIndex]==toBePrinted){
return tempIndex;
}
}
}
}
}
return tempIndex;
}
public static string stringReverseString1 (string str){
char[] chars = str.ToCharArray();
char[] result = new char[chars.Length];
for (int i =0, j = str.Length - 1; i < str.Length; i++, j--){
result[i] = chars[j];
}
return new string(result);
}
public static int[] GetCharFrequence(string str){
int []frq=new int[26];
int count=0;
for(int frqIndex=0;frqIndex<26;frqIndex++)
frq[frqIndex]='0';
char []temp=RemoveRepetetion(str).ToCharArray();
Array.Sort(temp);
for(int index=0;index<temp.Length;index++){
for(int matchIndex=0;matchIndex<str.Length;matchIndex++){
if(temp[index]==str[matchIndex]){
count++;
}
}
frq[temp[index]-97]=count/2;
count=0;
}
GetString(frq,temp,str);
return frq;
}
static string RemoveRepetetion(string str){
string newStr="";
foreach(char ch in str){
if(!(IsContainChar(newStr,ch)))
newStr+=ch;
}
return newStr;
}
static bool IsContainChar(string str,char character){
foreach(char ch in str){
if(ch==character)
return true;
}
return false;
}
public static int GetFrq(string str,char ch){
int frq=0;
for(int index=0;index<str.Length;index++){
if(ch==str[index])
frq++;
}
return frq;
}
static void Main(String[] args) {
string str=Console.ReadLine();
GetLexicographicallySmallestStr(str);
}
}Reverse Shuffle Merge Java Solution
import java.io.*;
import java.util.*;
import java.math.*;
public class Solution implements Runnable {
static BufferedReader in;
static PrintWriter out;
static StringTokenizer st;
static Random rnd;
private void solve() throws IOException {
int tests = 1;
for (int test = 0; test < tests; test++)
solveOne();
}
private void solveOne() throws IOException {
String s = nextToken();
s = reverseString(s);
final int alphaSize = 26;
int[] count = new int[alphaSize];
for (int i = 0; i < s.length(); i++)
++count[s.charAt(i) - 'a'];
int needLength = 0;
for (int i = 0; i < alphaSize; i++) {
if (count[i] % 2 != 0)
throw new AssertionError();
count[i] /= 2;
needLength += count[i];
}
StringBuilder result = new StringBuilder();
int[][] counts = new int[s.length()][alphaSize];
for (int i = s.length() - 1; i >= 0; i--) {
for (int j = 0; j < alphaSize; j++)
counts[i][j] = (i + 1 == s.length() ? 0 : counts[i + 1][j]);
counts[i][s.charAt(i) - 'a']++;
}
int leftPointer = 0;
for (int it = 0; it < needLength; it++) {
int resultIndex = -1;
for (int i = leftPointer; i < s.length(); i++) {
// out.println(it + " " + i + " " + resultIndex);
if (count[s.charAt(i) - 'a'] > 0) {
if (resultIndex == -1
|| s.charAt(i) < s.charAt(resultIndex)) {
if (isOk(count, counts[i]))
resultIndex = i;
}
}
}
result.append(s.charAt(resultIndex));
--count[s.charAt(resultIndex) - 'a'];
leftPointer = resultIndex + 1;
// out.println(resultIndex + " " + result);
// out.flush();
}
out.println(result);
}
private boolean isOk(int[] a, int[] b) {
for (int i = 0; i < a.length; i++)
if (a[i] > b[i])
return false;
return true;
}
private String reverseString(String s) {
return new StringBuilder(s).reverse().toString();
}
public static void main(String[] args) {
new Solution().run();
}
public void run() {
try {
in = new BufferedReader(new InputStreamReader(System.in));
out = new PrintWriter(System.out);
rnd = new Random();
solve();
out.close();
} catch (IOException e) {
e.printStackTrace();
System.exit(1);
}
}
private String nextToken() throws IOException {
while (st == null || !st.hasMoreTokens()) {
String line = in.readLine();
if (line == null)
return null;
st = new StringTokenizer(line);
}
return st.nextToken();
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
private long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
private double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
}
Reverse Shuffle Merge JavaScript Solution
'use strict';
const fs = require('fs');
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let inputString = '';
let currentLine = 0;
process.stdin.on('data', inputStdin => {
inputString += inputStdin;
});
process.stdin.on('end', _ => {
inputString = inputString.replace(/\s*$/, '')
.split('\n')
.map(str => str.replace(/\s*$/, ''));
main();
});
function readLine() {
return inputString[currentLine++];
}
// Complete the reverseShuffleMerge function below.
const alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'];
function reverseShuffleMerge(s) {
var { dict, skipDict } = buildDictionary(s);
var charList = [];
s.split('').reverse().forEach((c) => {
if (charList.length === 0) {
charList.push(c);
dict[c]--;
} else {
if (dict[c] == 0) {
skipDict[c]--;
} else {
while (charList.length > 0) {
let last = charList[charList.length - 1];
if (c < last && skipDict[last] > 0) {
skipDict[last]--;
dict[last]++;
charList.length--;
} else {
break;
}
}
charList.push(c);
dict[c]--;
}
}
});
return charList.join('');
}
function buildDictionary(s) {
let dict = {};
for (let i = 0; i < s.length; i++) {
let char = s.charAt(i)
if (dict[char] == undefined) {
dict[char] = 0.5;
} else {
dict[char] += 0.5;
}
}
return { dict, skipDict: { ...dict } }
}
function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);
const s = readLine();
let result = reverseShuffleMerge(s);
ws.write(result + "\n");
ws.end();
}Reverse Shuffle Merge Python Solution
from collections import Counter
original = s = input()
counter = Counter(s)
for k in counter:
counter[k] //= 2
word = ""
while len(word) < len(original) // 2:
for c in sorted(counter.keys()):
i = s.rfind(c)
left = Counter(s[:i + 1])
if all(k in left and left[k] >= counter[k] for k in counter):
word += c
s = s[:i]
counter[c] -= 1
if counter[c] == 0:
del counter[c]
break
print(word)
