Packing Problem

[Rob Cliffe]

I found Hen Hanna's "packing" problem to be an intriguing one: Given a 
list of words:
     ['APPLE', 'PIE', 'APRICOT', 'BANANA', 'CANDY']
find a string (in general non-unique) as short as possible which 
contains the letters of each of these words, in order, as a subsequence.
It struck me as being rather hard for a homework problem, unless I'm 
missing something blindingly obvious.
Here is what I came up with (I could have done with 
removeprefix/removesuffix but I'm stuck on Python 3.8 for now 🙁):

# Pack.py
def Pack(Words):
     if not Words:
         return ''
     # The method is to build up the result by adding letters at the 
beginning
     # and working forward, and by adding letters at the end, working 
backwards,
     # meanwhile shrinking the words in the list.
     Words = list(Words) # Don't mutate the original
     Initial = ''
     Final = ''
     while True:
         AnyProgress = False
         # It is safe to add an initial letter (of one or more of the 
words) if
         # EITHER    There is no word that contains it as
         #             a non-initial letter but not as an initial letter.
         #  OR       All words start with it.
         while True:
             FirstLetters = ''.join(w[0] for w in Words)
             FirstLetters = [ ch for ch in FirstLetters if
                 all(w[0]==ch for w in Words)
                 or not any(ch in w[1:] and w[0]!=ch for w in Words) ]
             if not FirstLetters:
                 break
             AnyProgress = True
             ch = FirstLetters[0]    # Pick one
             Initial += ch           # Build up the answer from the 
beginning
             Words = [ (w[1:] if w[0]==ch else w) for w in Words ]
             Words = [ w for w in Words if w != '']
             if not Words:
                 return Initial + Final
         # It is safe to add a final letter (of one or more of the words) of
         # EITHER    There is no word that contains it as
         #             a non-final letter but not as a final letter.
         #  OR       All words end with it.
         while True:
             LastLetters = ''.join(w[-1] for w in Words)
             LastLetters = [ ch for ch in LastLetters if
                 all(w[-1]==ch for w in Words)
                 or not any(ch in w[:-1] and w[-1]!=ch for w in Words) ]
             if not LastLetters:
                 break
             AnyProgress = True
             ch = LastLetters[0]     # Pick one
             Final = ch + Final      # Build up the answer from the end
             Words = [ (w[:-1] if w[-1]==ch else w) for w in Words ]
             Words = [ w for w in Words if w != '']
             if not Words:
                 return Initial + Final
         if not AnyProgress:
             break
     # Try all the possibilities for the next letter to add at the 
beginning,
     # with recursive calls, and pick one that gives a shortest answer:
     BestResult = None
     for ch in set(w[0] for w in Words):
             Words2 = list( (w[1:] if w[0] == ch else w) for w in Words )
             Words2 = [ w for w in Words2 if w != '' ]
             res = ch + Pack(Words2)
             if BestResult is None or len(res) < len(BestResult):
                 BestResult = res
     return Initial + BestResult + Final

print(Pack(['APPLE', 'PIE', 'APRICOT', 'BANANA', 'CANDY']))

The output:
BAPPRICNANADYOTLE
which has the same length as the answer I came up with trying to solve 
it with my unaided brain, which may or may not be reassuring 😂,
and also contains a much-needed BRANDY.
I expect there are simpler and more efficient solutions.
Best wishes
Rob Cliffe