Morgan and a String HackerRank challenge I am solving a HackerRank problem called 'Morgan and a String'.  Given two strings, each consisting of up to 105 uppercase characters, the task is to form the lexicographically smallest string from those letters by taking the first remaining character from either of the strings at each step.  Example, for input strings "ACA" and "BCF", the answer should be "ABCACF":



Jack    Daniel  Result
ACA     BCF
CA      BCF     A
CA      CF      AB
A       CF      ABC
A       CF      ABCA
        F       ABCAC
                ABCACF


Sample input, with one test case:

1
ACEG
BDFH


Output:

ABCDEFGH


I've solved it by writing my own code which works perfectly on smaller test cases. But when they run it against test cases which are approx 6000 characters long I get a runtime error. How can I increase the efficiency?



n=int(input())#number of pairs to input
for mn in range(n):
    a=input()# String1 in the pair
    b=input()#String2 in the pair
    la=[]
    lb=[]

    for i in range(max(len(a),len(b))):#creating lists with all possible elements by slicing off the characters
        la.append(a[i:])
        lb.append(b[i:])

    if len(a)&gt;len(b):#removes empty elements
        lb=[x for x in lb if x!='']
    else:
        la=[x for x in la if x!='']

    while True:#Create empty list for sorting the 0th elements of 'la' nd 'lb'
        temp=[]
        temp.append(la[0])
        temp.append(lb[0])
        temp=sorted(temp)
        print(temp[0][0],end='')#print the 1st character

        if(temp[0] in la):#removing the element after printing the first character
            la.pop(0)
        else:
            lb.pop(0)

        if len(la)==0:#breaks the while loop if a list gets empty
            print(temp[1],end='')
            break
        elif len(lb)==0:
            print(temp[1],end='')
            break
This is an improvement on @Toby's answer

Instead of str += char which allocates a new string you can yield the result and &quot;&quot;.join() it later on

Here's the problem: consider &quot;BAB&quot;, &quot;BAC&quot;. One would think to compare the two strings, see that BA-&gt;B is more minimal than BA-&gt;C. or you see that BA-&gt;B(end of string) is shorter than BA-&gt;(jump to other string)BA. Both of these are wrong, because we end up with BABBAC, instead of BABABC, which is more minimal (BABA &lt; BABB).
The z fixes things because it fixes the issue where we incorrectly choose BA-&gt;B\0 over BA(first stack)-&gt;(other stack)BA. BA-&gt;BA &lt; BA-&gt;Bz. Realistically what we should do during tiebreakers is jump to the other stack when one ends so we are comparing against BABB instead of BABz, but the z solution is faster.

Normally with the &quot;z&quot; fix you need to remove them from the end result, but because any uppercase char is lower then the lowercase &quot;z&quot; we know after len(a) + len(b) - 2 iterations only the 2 &quot;z&quot; strings remain in the resulting string. thus we only need to loop len(a) + len(b) - 2 times


Improved code
def morgan(a, b):
    a += &quot;z&quot;
    b += &quot;z&quot;
    for _ in range(len(a) + len(b) - 2):
        if a &lt; b:
            yield a[0]
            a = a[1:]
        else:
            yield b[0]
            b = b[1:]

def morgan_and_string(a, b):
    &quot;&quot;&quot;
    Return the lexicographically smallest string formed from the input strings, keeping each string
    in order in the result.

    Same length
    &gt;&gt;&gt; morgan_and_string(&quot;ACEG&quot;, &quot;BDFH&quot;)
    'ABCDEFGH'
    &gt;&gt;&gt; morgan_and_string(&quot;ABCD&quot;, &quot;ABCD&quot;)
    'AABBCCDD'

    Empty input
    &gt;&gt;&gt; morgan_and_string(&quot;ABCD&quot;, &quot;&quot;)
    'ABCD'
    &gt;&gt;&gt; morgan_and_string(&quot;&quot;, &quot;ABCD&quot;)
    'ABCD'

    Different length
    &gt;&gt;&gt; morgan_and_string(&quot;Z&quot;, &quot;ABCD&quot;)
    'ABCDZ'
    &gt;&gt;&gt; morgan_and_string(&quot;ABCD&quot;, &quot;Z&quot;)
    'ABCDZ'

    Descending strings
    &gt;&gt;&gt; morgan_and_string(&quot;BA&quot;, &quot;BA&quot;)
    'BABA'

    &gt;&gt;&gt; morgan_and_string(&quot;ZAX&quot;, &quot;ZAY&quot;)
    'ZAXZAY'
    &gt;&gt;&gt; morgan_and_string(&quot;ZAY&quot;, &quot;ZAX&quot;)
    'ZAXZAY'

    Proper prefix
    &gt;&gt;&gt; morgan_and_string(&quot;BABC&quot;, &quot;BA&quot;)
    'BABABC'
    &gt;&gt;&gt; morgan_and_string(&quot;CABC&quot;, &quot;CA&quot;)
    'CABCAC'
    &gt;&gt;&gt; morgan_and_string(&quot;BAAC&quot;, &quot;BA&quot;)
    'BAABAC'
    &quot;&quot;&quot;
    return &quot;&quot;.join(morgan(a, b))

if __name__ == '__main__':
    import doctest
    doctest.testmod()