Skip to content
  • Home
  • Contact Us
  • About Us
  • Privacy Policy
  • DMCA
  • Linkedin
  • Pinterest
  • Facebook
thecscience

TheCScience

TheCScience is a blog that publishes daily tutorials and guides on engineering subjects and everything that related to computer science and technology

  • Home
  • Human values
  • Microprocessor
  • Digital communication
  • Linux
  • outsystems guide
  • Toggle search form
HackerRank Reverse Shuffle Merge Problem Solution

HackerRank Reverse Shuffle Merge Solution

Posted on June 11, 2023June 11, 2023 By Yashwant Parihar No Comments on HackerRank Reverse Shuffle Merge Solution

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

Table of Contents

  • Reverse Shuffle Merge C Solution
  • Reverse Shuffle Merge C++ Solution
  • Reverse Shuffle Merge C Sharp Solution
  • Reverse Shuffle Merge Java Solution
  • Reverse Shuffle Merge JavaScript Solution
  • Reverse Shuffle Merge Python 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 Tags:C, cpp, CSharp, Hackerrank Solutions, java, javascript, python

Post navigation

Previous Post: HackerRank Cutting Boards Problem Solution
Next Post: HackerRank Goodland Electricity Problem Solution

Related Posts

HackerRank Tripartite Matching Problem Solution HackerRank Tripartite Matching Problem Solution c
HackerRank Bricks Game Problem Solution HackerRank Bricks Game Problem Solution c
HackerRank Ashton and String Problem Solution HackerRank Ashton and String Problem Solution c
HackerRank Subarray Division Problem Solution HackerRank Subarray Division Problem Solution c
HackerRank Letter Islands Problem Solution HackerRank Letter Islands Problem Solution c
HackerRank Zurikela's Graph Problem Solution HackerRank Zurikela’s Graph Problem Solution c

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick Your Subject
Human Values

Copyright © 2023 TheCScience.

Powered by PressBook Grid Blogs theme