Jack and Daniel are friends. Both of them like letters, especially upper-case ones. They are cutting upper-case letters from newspapers, and each one of them has his collection of letters stored in a stack.
One beautiful day, Morgan visited Jack and Daniel. He saw their collections. He wondered what is the lexicographically minimal string made of those two collections. He can take a letter from a collection only when it is on the top of the stack. Morgan wants to use all of the letters in their collections.
As an example, assume Jack has collected
a = [A, C, A] and Daniel has
b = [B, C, F]. The example shows the top at index
0 for each stack of letters. Assembling the string would go as follows:
Jack Daniel Result ACA BCF CA BCF A CA CF AB A CF ABC A CF ABCA F ABCAC ABCACF
Note the choice when there was a tie at CA and CF.
Complete the morganAndString function in the editor below. It should return the completed string.
morganAndString has the following parameter(s):
a: a string representing Jack’s letters, top at index
b: a string representing Daniel’s letters, top at index
I’m providing the solution for Python and JS, please leave on the comments if you found a better way.
The secret to solving the problem is to realize that we don’t need to compare a sting at a time, but rather the whole string which is left, that way we guarantee always taking the smaller one in the case of ties.