So... the only way to solve this task is to look at the answers... The problem is described leaving several ways to solve it. And then test cases are riddled with assumptions on how the programmer will solve this problem.

Also, all examples show the code failing at full string and not a prefix. So in my code I only asked a question - Does this string have a prefix in a given List?

It does say to output "first string that it fails at". I can check the strings in whatever order I want (or think in what order it would usually run faster). But whatever, examples did not sort the List too.

So I solve the problem and then hidden tests say my answers are wrong because half of them expect me to return a prefix and not a full string... It assumed that I would check if the string is a prefix or has a prefix, not just one of those questions even if asking only one of the questions still solves the problem and is faster.

And it also assumes, that I will check for prefixes only in the entries preceding the string being checked and not a whole List at once.

Also, why in all tasks they say array and then give a list?

This is a very poorly worded problem in my opinion, and the given test cases are unclear / incomplete.

There are two things that you need to check for as you iterate through the list of original input words:

1. Is the current input word a prefix of any of the previously checked words? If yes, print "BAD SET" and print the current word (which is a prefix, this is what I think is very unclear from the description)

2. Is a prefix of the current word one of the words I've previously processed? If yes, print "BAD SET" and print the current word (not the prefix).

To check these two conditions I used a std::multiset to keep track of the input words (to be able to detect duplicate words), and a std::set to keep track of all previous prefixes to check input words against (I don't care about duplicates here, so a normal set will work just fine).

See my solution in C++14:

void noPrefix(vector<string> words) {

    multiset<string> words_to_check; // set of words to add to as we process the original list, this must be a multiset so we can detect duplicate words

    set<string> all_prefixes; // set of all prefixes of words we've already checked, this allows us to see if a new word in the list is a prefix to a word we've already checked

    // cycle through all the words
    for(auto w : words)
    {
        // check if current word is a prefix of other words
        if(all_prefixes.find(w) != all_prefixes.end())
        {
            // we found the prefix in the original word set
            cout << "BAD SET" << endl;
            cout << w << endl;
            return;
        }

        // check all 'prefixes' of current word in words_to_check set
        string prefix = w;
        while (!prefix.empty()) {
            // insert each prefix in list of prefixes to check future words against
            all_prefixes.insert(prefix);

            // check to see if the current prefix matches a word we've seen before
            if(words_to_check.find(prefix) != words_to_check.end();
            {
                // we found the prefix in the original word set
                cout << "BAD SET" << endl;
                cout << w << endl;
                return;
            } else {
                // remove one character from back of prefix, creating a new prefix
                prefix.pop_back();
            }
        }
        // append the most recently checked word to my list of full words to check on future prefixes
        words_to_check.insert(w);
    }
    // if we've checked every word in the original list and not found any prefixes, we must have a good set
    cout << "GOOD SET" << endl;
}

Straightforward Java soluion

this solution uses a TreeSet --this is all that is needed.

A TreeSet holds items in sorted order; so as I process items from the original input list, I do the following; find the least element in this set greater than or equal to the given element, or null if there is no such element. find the greatest element in this set less than or equal to the given element, or null if there is no such element. check if the current word being processed is (or has) a prefix to (for) an already processed word in the set. if #3 is false, then add current word to the set of processed words. [this must be done last before the loop continues, so that we can catch & return the duplicate -since the duplicate will be a valid answer]

    public static void noPrefix(List<String> words) {
    // Write your code here
        TreeSet<String> treeSet = new TreeSet<>();
        for (int i = 0; i < words.size(); i++) {
            String word = words.get(i);
            String next = treeSet.ceiling(word);
            String prev = treeSet.floor(word);
            
            if ((next != null && next.startsWith(word)) || (prev != null && word.startsWith(prev))) {
                System.out.println("BAD SET");
                System.out.println(word);
                return;
            }
            
            treeSet.add(word);
        }
        
        System.out.println("GOOD SET");
    }

Don't overcomplicate it!

Hint: use 2 hashtables (HT)

If you wanna read more to know my solution then continue.

Honestly, the task is really simple if you think about it carefully. You will need to find the first instance that will make a bad set, none found then it will be a good set. As the order matter and you need the first instance (hence, no sorting should be done), you should approach it will linear approach, or in simple words, go from the beginning to the end. When you examine an instance, you need to think: will it make a bad set (and return immediately) or not; and there are 2 cases can happen: it is the prefix of the previous ones or one of the previous ones is the prefix of it. So the key here is to store the previous ones so the later can check. And it hit me, HASHTABLE, 2 HASHTABLES, one for storing the prefixes (break a word into prefixes) and one just store the previous words. And you only need to check the hashtables and update them on your go. Voila, done! Technically speaking, this is O(n) because accessing the HTs is O(1) and you can argue that the loop over each string is O(1) as well as each string at max is 60 (kinda why this algo works haha).

Below would be the solution in Python

def noPrefix(words):
    ht_prefix = {}
    ht_word = {}
    for w in words:
        check = ''
        if w in ht_prefix:
            print("BAD SET")
            print(w)
            return
        for l in w:
            check += l
            ht_prefix[check] = 1
            if check in ht_word:
                print("BAD SET")
                print(w)
                return
        ht_word[w] = 1
    print("GOOD SET")

The description is not clear.

I have been trying:

• first prefix = WRONG
• first prefixed word = WRONG
• first prefix after prefixed word or prefixed word after prefix = BINGO !!