Morgan and a String!

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.

Newsletter

Subscribe to my weekly newsletter for developers and builders and get a weekly email with relevant content.

    You can learn more about what to expect in these emails here.