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.