We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Greedy
  4. Reverse Shuffle Merge
  5. Discussions

Reverse Shuffle Merge

Problem
Submissions
Leaderboard
Discussions
Editorial
Topics

Sort 196 Discussions, By:

votes

Please Login in order to post a comment

  • AbhishekVermaIIT
    7 years ago+ 21 comments

    For guys looking for simpler solution with low complexity, here's my submission (40 lines of code in C and 0s execution time for all test cases).


    If the input string is S and the required answer is A, then the basic idea is as follows :

    1) Store the count of each character (a to z) in S.

    2) Update the count of characters required for A by dividing by 2.

    3) Select each character for A by parsing S from right to left.

    4) One "can" afford to "not select" a character, if its required-count for A will be fulfilled even after leaving it.

    5) Considering point 4, always select smallest character if possible.

    6) If a character can't be left (point 4 invalid), select the smallest character seen so far (even if it is not smallest for the entire string).

    7) Ignore characters not required for A anymore.


    Informative Tweets for Inquisitive Minds

    125|
    Permalink
    View more Comments..
  • magazinov_al
    4 years ago+ 4 comments
    Sample Input 2: aeiouuoiea
    Sample Output 2: eaid
    

    Isn't this an obvious error? For instance, there is no 'd' character in the input...

    48|
    Permalink
    View more Comments..
  • denis631
    4 years ago+ 8 comments
    1. Built frequency hash-map for char and occurences. Original word has half of the occurence of every char
    2. Reverse the original string and try to construct the smallest lexicographic one
    3. While iterating, use a stack (the idea somehow resembles the largest rectangle problem, from stack category).
    4. If the new char occurs already n/2 times, where n = frequency of the original / 2, then skip this char, since we can not, nor we should push it to the stack
    5. else pop chars from the stack, if: stack is not empty, top char stack is greater than the new char and by removing the top char we still can build the word with desired frequency

    Python solution, inspired by @mbrotma1's solution.

    def frequency(s):
        res = defaultdict(int)
        for char in s:
            res[char] += 1
        return res
    
    # Complete the reverseShuffleMerge function below.
    def reverse_shuffle_merge(s):
        char_freq = frequency(s)
        used_chars = defaultdict(int)
        remain_chars = dict(char_freq)
        res = []
        
        def can_use(char):
            return (char_freq[char] // 2 - used_chars[char]) > 0
        
        def can_pop(char):
            needed_chars = char_freq[char] // 2
            return used_chars[char] + remain_chars[char] - 1 >= needed_chars
        
        for char in reversed(s):
            if can_use(char):
                while res and res[-1] > char and can_pop(res[-1]):
                    removed_char = res.pop()
                    used_chars[removed_char] -= 1
                
                used_chars[char] += 1
                res.append(char)
            
            remain_chars[char] -= 1
        
        return "".join(res)
    
    29|
    Permalink
    View more Comments..
  • TheMana
    3 years ago+ 4 comments

    Plain english explanation of this problem

    So basically, we have a string A for which we use to generate another string s, where s = merge(reverse(A), shuffle(A))

    Notice that if we reverse s (let's call this new string s') , the resulting string will contain the exact order of the characters in the original string A . The question now is how can we extract the original characters of A from s'?

    Well, that is easy to do. We already know that the length of s' is twice the length of A. So, A should contain half of each character count in the string s' .

    A naive way to obtain A, therefore, is to iterate through s', adding each character to a new string A, so long the total of each character added to A does not violate the condition above.

    A second way which adds a bit of complexity to the problem is doing the same thing as in 1. with the following requirement: the character at position i, A[i], is the minimum/smallest out of all possible variations of A that can generate s. And this is what this question is also about.

    Python code here

    		
    
    def reverseShuffleMerge(s):
        # Total character counts in s
        char_count = Counter(s)
        
        # Character counts we need in our final string
        string_chars = { 
            char: int(count / 2) for char, count in char_count.items() 
        }
            
        # Character counts we need in the shuffled 
        # version of our original string 
        shuffled_chars = { 
            char: int(count / 2) for char, count in char_count.items() 
        }
        
        string = []
    		
        for char in reversed(s):
            if string_chars[char] > 0:
                # See if this character should appear before any 
                # previous ones. Basically, if this char is smaller 
                # than the previous char, and the previous char 
                # still occurs in the chars of the shuffled string, 
                # we can the safely replace the previous char 
                # with this one. That's so because we should be 
                # able to still create a valid string which contains
                # both characters although the order will differs.
                while string and string[-1] > char and shuffled_chars[string[-1]] > 0:
                    removed = string.pop()
                    string_chars[removed] += 1
                    shuffled_chars[removed] -= 1
                
                string.append(char)
                string_chars[char] -= 1
            else:
                shuffled_chars[char] -= 1
    
        return ''.join(string)
    
    22|
    Permalink
    View more Comments..
  • Tuxdude
    7 years ago+ 4 comments

    Was one of the toughest challenges in terms of amount of time it took to get all the boundary conditions correct.

    I went through the Editorial after I solved the problem, although the approach itself is somewhat OK to understand by reading the editorial, I'm sorry to say that the code given is hardly readable. Especially using single letter variable names for arrays, and even more - using the same variable names for an array declared in the beginning of the code and re-using the same variable for the loop iterator as well, just adds more confusion when looking at the code. I believe it could be improved to make it easier to understand for a reader who did not solve the problem on his/her own.

    Here is my submission if someone wants to look at an easier to read code using a similar approach mentioned in the editorial.

    13|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature