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.

def morgan(a, b):
    a += "z"
    b += "z"
    for _ in range(len(a) + len(b) - 2):
        if a < b:
            yield a[0]
            a = a[1:]
        else:
            yield b[0]
            b = b[1:]

def morganAndString(a, b):
    return ''.join(morgan(a, b))

function* morgan(a, b) {
    a += "z";
    b += "z";
    const l = a.length+b.length-2;
    for (var i=0; i<l;i++) {
        if (a < b) {
            yield a[0]
            a = a.slice(1)
        } else {
            yield b[0]
            b = b.slice(1)
        }
    }
}

function morganAndString(a, b) {
    return Array.from(morgan(a, b)).join('')
}