Lexicographical Merge

Problem Statement

Lexicographical Merge Problem Description You are building your own programming language and want its string merge function to behave a little differently from the usual one. A merge of two strings s1 and s2 places the characters of s2 between the characters of s1 so that the characters of each string keep their original relative order. The merge is built one character at a time: at every step, look at the first remaining character a of s1 and the first remaining character b of s2 , take the smaller one and append it to the result. When one string runs out, append the rest of the other string. In your language, characters are not compared in plain alphabetical order. Instead: 1. A character is smaller if it occurs fewer times in its own original string ( a is counted in the whole of s1 , b in the whole of s2 ; the counts never change while merging). 2. If the two counts are equal, the alphabetically smaller character is smaller. 3. If the counts and the characters are both equal, take