from collections import Counter

def reverseShuffleMerge(s):
    char_counts = Counter(s)
    required = Counter()
    for key, value in char_counts.items():
        required[key] = value // 2
    last_char = s[-1]
    char_counts[last_char] -= 1
    required[last_char] -= 1
    result = [last_char]
    for i in range(len(s)-2, -1, -1):
        char = s[i]
        char_counts[char] -= 1
        if not required[char]:
            pass
        elif (not result) or (char >= result[-1]):
            result.append(char)
            required[char] -= 1
        else:
            while result and char < result[-1] and char_counts[result[-1]] >= required[result[-1]] +1:
                old_char = result.pop(-1)
                required[old_char] += 1
            result.append(char)
            required[char] -= 1
    return "".join(result)

def reverseShuffleMerge(s):
    from collections import Counter

    # Calculate the frequency of each character in s
    freq = Counter(s)
    
    # Calculate the required frequency for A
    required = {char: freq[char] // 2 for char in freq}
    
    # Initialize counts of used characters
    used = {char: 0 for char in freq}
    
    result = []
    # Iterate over the string in reverse order
    for char in reversed(s):
        if used[char] < required[char]:
            # Ensure that we are making the lexicographically smallest result
            while result and result[-1] > char and used[result[-1]] + freq[result[-1]] > required[result[-1]]:
                removed_char = result.pop()
                used[removed_char] -= 1

            result.append(char)
            used[char] += 1
        
        # Decrease the frequency count as we have processed this character
        freq[char] -= 1
    
    # Convert result list to a string and return
    return ''.join(result)

from collections import Counter

def reverseShuffleMerge(s):
    # find character frequencies in the desired string A
    freq = {key: val // 2 for key, val in Counter(s).items()}

    # repeat gready approach until solution is complete
    solution = []
    n = len(s)
    while len(solution) < n // 2:
        left_freq = Counter(s)
        next_char = {}
        min_char = '~'
        # search original string S backwards
        for index in range(len(s)-1, -1, -1):
            char = s[index]
            # it is possible to take this char as the next one
            if char not in next_char and freq[char] > 0:
                next_char[char] = index
                min_char = min(min_char, char)
            # there's not enough letters available to the left
            left_freq[char] -= 1
            if left_freq[char] < freq[char]:
                break
        # add minimal char as the next one (greedy)
        solution += min_char
        freq[min_char] -= 1
        s = s[0:next_char[min_char]]

    return "".join(solution)