Using deque for composing a string from 2 alternating stacks We have 2 strings, say "JACK" and "DANIELS". We create two stacks from these strings, and then loop over them comparing first elements: whichever of the 2 goes first in lexicographic order gets popped from its stack and added to a string (the second value is left alone). So it goes, until we end up with a string containing all the elements from both stacks. In this example it would be "DAJACKNIELS"

My solution takes advantage of the fact that min function, when applied to deque() objects, returns the one whose first element goes lexicographically first. As it happens, it works well enough for small testcases, but fails large ones, for it takes all the memory it can get and then some.

Perhaps, something can be improved in my code, or there's a better solution altogether (like, without a while loop).

def morgan(a, b):
    string = ""
    stack_a = deque()
    stack_b = deque()

    stack_a.extend(a)
    stack_b.extend(b)
    while True:
        if len(stack_a) != 0 and len(stack_b) != 0:
            if stack_a == min(stack_a, stack_b):
                string += stack_a.popleft()
            else:
                string += stack_b.popleft()
        elif len(stack_a) == 0 and len(stack_b) == 0:
            break
        elif len(stack_a) == 0:
            string += stack_b.popleft()
        elif len(stack_b) == 0:
            string += stack_a.popleft()
    return(string)


Example of a large testcase:

string a: https://pastebin.com/raw/pebMbcA6
string b: https://pastebin.com/raw/bwNEqJcr
There is no need to read the whole string into a deque. Just iterate over the strings using iterators. The only gotcha is handling the fact that either of the strings can be empty at the beginning and that one can be exhausted before the other.

def _morgan(a, b):
    a, b = iter(a), iter(b)
    try:
        x = next(a)
    except StopIteration:
        yield from b
        return
    try:
        y = next(b)
    except StopIteration:
        yield x
        yield from a
        return
    while True:
        if x &lt;= y:  # `&lt;=` because that's what `min` does
            yield x
            try:
                x = next(a)
            except StopIteration:
                yield y
                yield from b
                return
        else:
            yield y
            try:
                y = next(b)
            except StopIteration:
                yield x
                yield from a
                return


def morgan(a, b):
    return "".join(_morgan(a, b))


Note that both the original strings and the resulting string still need to fit into memory for this to work. If you only need to iterate over the resulting string, use only the private function. In that case the original strings still need to fit into memory, unless you also have them as generators (e.g. by streaming the contents from the URLs):

import requests

def stream(url, chunk_size=1000):
    with requests.get(url, stream=True) as r:
        for chunk in r.iter_content(chunk_size=chunk_size, decode_unicode=True):
            yield from iter(chunk)

if __name__ == "__main__":
    a = stream("https://pastebin.com/raw/pebMbcA6")
    b = stream("https://pastebin.com/raw/bwNEqJcr")
    c = _morgan(a, b)
    while (chunk := "".join(islice(c, 1000))):
        print(chunk, end='')
    print()


This works on my machine with the given strings, but so does the morgan function I defined above.



Note that you need Python 3.8+ for the walrus operator :=. With earlier Python versions it is slightly more verbose:

 if __name__ == "__main__":
    a = stream("https://pastebin.com/raw/pebMbcA6")
    b = stream("https://pastebin.com/raw/bwNEqJcr")
    c = _morgan(a, b)
    chunk = "".join(islice(c, 1000))
    while chunk:
        print(chunk, end='')
        chunk = "".join(islice(c, 1000))
    print()