I have an issue with the problem description, as it is tailored to a specific solution. Not only having to print "the string being checked" instead of specifically the prefix or string that contains the prefix is inconsistent, but correct answers are marked as wrong. For example, in the test case they show:

4 aab aac aacghgh aabghgh

there are actually FOUR correct answers: aab is a prefix of aabghgh and aac is a prefix of aacghgh. Since we can print any string of the prefix-prefixed pair, we could technically print any of these and be correct. HOWEVER, only BAD SET aacghgh is correct, because they assume we will be solving the problem in a specific way.

Good problem but bad solution criteria, in my opinion.

I'm in doubt here. Following the problem description and samples explanations, actual test case 1 should print BAD SET with the third string "edchgb", but the test case expect an output of "d" which is evaluated later. Also, "d" is the prefix, not the string that contains it. Can someone explain me this?

my Python 3 attempt by incrementally inserting words into a trie (thanks to inspiration from many of you guys) (must be some other "cleaner" way to do the create dict if not exists step, but I prefer readability in my own terms XD):

edit: simplified and updated thanks to @dgzwiro !

def noPrefix(words):
    #Write your code here
    _end = "_end"
    trie = {}
    
    #return the current word where the check fails
    def bad(s):
        print("BAD SET")
        print(s)
    
    #incremental insertion of words
    for word in words:
        current = trie
        #for each word, insert and change current map/dict per letter
        for c in word:
            #FAIL: a processed word is the prefix of the current word
            if _end in current:
                bad(word)
                return
            #create map/dict if missing
            if c not in current:
                current[c] = {}
            current = current[c]
        
        #FAIL: current word map/dict is not empty
        #meaning either:
        #- current word was already inserted in the trie
        #- current word was a prefix of previously inserted words
        if len(current) > 0:
            bad(word)
            return
        
        #mark the current node where the current word ends here
        current[_end] = _end
    print("GOOD SET")

I'd love to hear some opinions on my solution.

def noPrefix(words): word_dict = dict()

for i, word in enumerate(words):
    if word in word_dict:
        word_dict[word].append(i)
    else:
        word_dict[word] = [i]

bad_ind = float('inf')
for i, word in enumerate(words):
    if i == bad_ind:
        break

    # Check substrings
    for j in range(len(word)-1):
        if word[0:j+1] in word_dict:
            bad_ind = min( bad_ind, max(i, word_dict[word[0:j+1]][0]) )

    # Check if full string repeats
    if len(word_dict[word]) > 1:
        bad_ind = min(bad_ind, word_dict[word][1])

if bad_ind == float('inf'):
    print("GOOD SET")
else:
    print("BAD SET")
    print(words[bad_ind])

return

Tried using .sort() such that the solution boils down to comparing neighbouring words. Unfortunately this violates the "tested first" condition due to the reordering of words:

def noPrefix_fail(words: list) -> None:
    words.sort()    # sort leixcographically
    for w1, w2 in zip(words, words[1:]): # sliding window of word pairs
        if w2.startswith(w1):
            print("BAD SET")
            print(w1)   # incorrect due to .sort()
            return
    print("GOOD SET")