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.

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('')
}

Juan Cruz Martinez

Juan has made it his mission to help aspiring developers unlock their full potential. With over two decades of hands-on programming experience, he understands the challenges and rewards of learning to code. By providing accessible and engaging educational content, Juan has cultivated a community of learners who share their passion for coding. Leveraging his expertise and empathetic teaching approach, Juan has successfully guided countless students on their journey to becoming skilled developers, transforming lives through the power of technology.