HackerRank Reverse Shuffle Merge Problem Solution

HackerRank Reverse Shuffle Merge Solution

Yashwant Parihar,

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
HackerRank Reverse Shuffle Merge Problem Solution
HackerRank Reverse Shuffle Merge Problem Solution

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)
c C# C++ HackerRank Solutions java javascript python