Morgan and a String!

Problem

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.

Function Description

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 0 b: a string representing Daniel’s letters, top at index 0

Read more on the challenge page…

My Solution

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.