How to find the missing letters of an ascending order arranged word in Python?

The problem statement is as follows:

A word (list) is arranged in ascending order. Now some of the letters of the word are masked while some letters are visible. My task is to make a list of all the letters which aren't present in the word such that the ascending order condition of the word is maintained.

To give an example: consider the word = ['*', '*', 'd', '*', '*', 'm']. Now here the first two blanks can only have letters - a, b or c while the two blanks towards the end can take letters - e, f, g, h, i, j, k, l

The existing letters in the word can't be used to fill the blanks. To solve this I have tried to write the following code, however there's some glitch. Some help would be great!

letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
word = ['*', '*', 'd', '*', '*', 'm']

if '*' not in word:
    for i in range(len(word)):
        if word[i] != '*':
            for j in range(len(word)):
                if word[j] == '*' :
                    if j< i:       #means the left part of the word is empty
                        for a in letters:
                            if a < word[i]:
                                new_left_letters.append(a)
                    elif j>i:         #means the right part of the word is empty
                        for a in letters:
                            if a > word[i]:
                                new_right_letters.append(a)
                        
    final_letters = new_left_letters + new_right_letters 

else:
    final_letters = letters     #means the entire letter is empty

print(final_letters)

Let's say a 'gap' is one or more consecutive masked letters, bounded on both ends by either an unmasked letter or one of the ends of the input array.

We can solve our gaps independently, then multiply them to get the final results.

Say we're solving a gap of length r which has k >= r letters to choose from (if k < r then there's no solution). The count of possible solutions is choose(r, k).

To enumerate these, use itertools.

combinations('valid_letters', r)

E.g.,

combinations('ABCD', 2) = AB AC AD BC BD CD

Once you've done this for each gap, you need to combine every valid solution for gap 1 with every valid solution for gap 2 and so on.

Here is how I attacked this question!

master_letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
word_letters = ['*', '*', 'd', '*', '*', 'm']

alphabets = []

previous_letter_index = 0 # will hold the index of the last resolved letter

def find_next_letter(word_letter, word_letters):
    found_wl = False
    for i in range(len(word_letters)):
        if found_wl and word_letters[i] != '*':
            return word_letters[i]
        elif word_letters[i] == word_letter:
            found_wl = True
    return -1

for i, word_letter in enumerate(word_letters):
    if word_letter != '*':
        # find the available letters for the * slots prior to this letter
        print(f"Found letter: {word_letter}")
        master_letter_index = master_letters.index(word_letter)
        print(f"Master index: {master_letter_index}")
        available_letters = master_letters[previous_letter_index:master_letter_index]
        print(f"Available letters: {available_letters}")

        # If there is another letter in the word, restrict the available letters.
        next_letter = find_next_letter(word_letter, word_letters)
        if previous_letter_index != 0 and next_letter != -1:
            for _ in range(previous_letter_index, i):
               alphabets.append(available_letters[:available_letters.index(next_letter)])
        else:
            for _ in range(previous_letter_index, i):
                alphabets.append(tuple(available_letters))

        previous_letter_index = master_letter_index

print(sorted(list(set(alphabets)), key=lambda x: x[0]))