Reverse Shuffle Merge

Given a string, , we define some operations on the string as follows:

a. denotes the string obtained by reversing string . Example:

b. denotes any string that's a permutation of string . Example:

c. denotes any string that's obtained by interspersing the two strings & , maintaining the order of characters in both. For example, & , one possible result of could be , another could be , another could be and so on.

Given a string such that for some string , find the lexicographically smallest .

For example, . We can split it into two strings of . The reverse is and we need to find a string to shuffle in to get . The middle two characters match our reverse string, leaving the and at the ends. Our shuffle string needs to be . Lexicographically , so our answer is .

Function 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 .

Constraints

contains only lower-case English letters, ascii[a-z]

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: gge.

'egg' < 'gge'

Sample Input 1

abcdefgabcdefg

Sample Output 1

agfedcb

Explanation 1

Split the string into two strings with like characters: and .
Reverse =
Shuffle can be
Merge to bcdefga

Sample Input 2

aeiouuoiea

Sample Output 2

aeiou

Explanation 2

Split the string into groups of like characters:
Reverse =
These merge to uoiea