class TrieNode {
    public isWord: boolean;
    public data: string;
    public children: Record<string, TrieNode> = {};
    
    constructor(isWord: boolean, data: string) {
        this.isWord = isWord;
        this.data = data;
    }
}

class PrefixTrie {
    private trie: TrieNode = new TrieNode(false, '');
    public children: Record<string, TrieNode> = {};
    
    /**
     * insertWord
     * @summary
     * Insert word in trie, return true or false depending on if prefix or duplicate word is found
     */
    insertWord(word: string): boolean {
        let prefixDetected = false;
        let curr = this.trie;
        for (let i = 0; i < word.length; i ++) {
            const char = word[i];
            /** Case: curr node is prefix (i < word.length - 1) or duplicate of inserted word (i = word.length - 1) */
            if (curr.isWord) { 
                prefixDetected = true 
            };
            if (!(char in curr.children)) {
                const isWord = i === word.length - 1;
                curr.children[char] = 
                    new TrieNode(isWord, word.substring(0, i + 1))
            } else if (i === word.length - 1) {
            /** Case: inserted word is prefix of another word (reached end of inserted word and curr has last char of inserted word in children) */
                prefixDetected = true;
            }
            curr = curr.children[char];
        }
        return prefixDetected;
    }
}



/*
 * Complete the 'noPrefix' function below.
 *
 * The function accepts STRING_ARRAY words as parameter.
 * Time complexity: O(N * M), N = number of strings, M = average length of string
 * Space complexity: O(N * M), N = number of strings, M = average length of string
 */
function noPrefix(words: string[]): void {
    let isGoodSet = true;
    const prefixTrieImpl = new PrefixTrie();
    let failPointIndex: number | undefined = undefined;
    for (let i = 0; i < words.length; i ++) {
        const prefixOrDuplicateFound = prefixTrieImpl.insertWord(words[i]);
        if (prefixOrDuplicateFound) {
            console.log('BAD SET');   
            console.log(words[i]);
            return;
        }
    }
    console.log('GOOD SET');

}

public static void noPrefix(List<String> words) {

        TrieNode root = new TrieNode(' ');

        for (String s : words) {
            TrieNode trav = root;
            for (char c : s.toCharArray()) {
                if (!trav.next.containsKey(c)) {
                    trav.next.put(c, new TrieNode(c));
                    trav = trav.next.get(c);
                } else {
                    trav = trav.next.get(c);
                    if (trav.isEndNode) {
                        System.out.println("BAD SET");
                        System.out.println(s);
                        return;
                    }
                }
            }
            trav.isEndNode = true;
        }
        System.out.println("GOOD SET");
    }

}

class TrieNode{
    final char c;
    Map<Character, TrieNode> next;

    boolean isEndNode = false;

    TrieNode(char c) {
        this.c = c;
        next = new HashMap<>();
    }
}

void noPrefix(vector<string> words) 
{
    int letterCount = 0;
    for (int i = 0; i < words.size(); i++) 
    {
        int j = 0;
        int k = 0;
        int z = 0;
        while (z < i) 
        {
            if (j < words[z].size() && k < words[i].size()) 
            {
                if (words[z][j] == words[i][k]) 
                {
                    letterCount++;
                    j++;
                    k++;
                    if (letterCount == words[z].size() || letterCount == words[i].size()) 
                    {
                        cout << "BAD SET\n"<< words[i];
                        return;
                    }
                    
                }
                else 
                {
                    letterCount = 0;
                    j = 0;
                    k++;
                }
            }
            else
            {
                letterCount = 0;
                j = 0;
                k = 0;
                z++;               
            }
        }

class TrieNode {
    
    public Dictionary<char, TrieNode> children {get;set;}
    public bool IsLeaf {get;set;} = false;
    public string Word {get;set;} = string.Empty;
    
    public TrieNode(){
        children = new Dictionary<char, TrieNode>();
    }
    
}

class Trie{
    
    public TrieNode root {get;set;}
    
    public Trie(){
        root = new TrieNode();
    }
    
    public bool AddWord(string word){
        TrieNode current = root;
        foreach(char c in word.ToCharArray()){
            if(!current.children.ContainsKey(c)){
                current.children.Add(c, new TrieNode());
                current = current.children[c];
            } else {
                current = current.children[c];
                //if current node already exists, and is marked as a leaf
                // this means that a prefix for the current word already exists
                if(current.IsLeaf){
                    Console.WriteLine("BAD SET");
                    Console.WriteLine(word);
                    return false;
                }
            }
        }
        
        // if current node has children, this means that the current word is a prefix for a word that already exists
        if(current.children.Count > 0){
            Console.WriteLine("BAD SET");
            Console.WriteLine(word);
            return false;
        }
        
        current.IsLeaf = true;
        current.Word = word;
        
        return true;
    }
}
class Result
{

    /*
     * Complete the 'noPrefix' function below.
     *
     * The function accepts STRING_ARRAY words as parameter.
     */

    public static void noPrefix(List<string> words)
    {
        Trie trie = new Trie();
        foreach(string word in words){
            if(!trie.AddWord(word)){
                return;
            }
        }
        Console.WriteLine("GOOD SET");
    }

}

def noPrefix(words):
    # Write your code here
    n = len(words)
    length = [item for item in range(0,n,1)]
    length[0] = len(words[0])
    for i in range(1,n,1):
        length[i] = len(words[i])
        for j in range(0,i,1):
            a = min(length[i], length[j])
            if words[i][0:a] == words[j][0:a]:
                print("BAD SET")
                print(words[i])
                return 
    print("GOOD SET")