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))
If you want to learn more about generators on Python, check out my article How to Use Generator and yield in Python
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('')
}
If you want to learn more about generators on Python, check out my article How to Use Generator and yield in JavaScript
Join more than a thousand developers!
Subscribe now to our free, weekly e-mail with the best new articles, courses, and special bonuses.
We won't send you spam. Unsubscribe at any time.