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

Sample Input 2: aeiouuoiea
Sample Output 2: eaid

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

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)

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)

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.