6061626364656667686970717273747576
# Class to represent each node of the Trie
class TrieNode:
    def __init__(self):
        # Indicates end of a valid word
        self.is_end = False  
        # Dictionary to store children
        self.children = {}   


# Class that contains only logic; no root stored
class Solution:
    # Insert a word into the Trie
    def insert(self, root, word):
        # Start from the root
        node = root

        # Traverse each character of the word
        for ch in word:
            # If child for character doesn't exist, create a new node
            if ch not in node.children:
                node.children[ch] = TrieNode()

            # Move to the next node
            node = node.children[ch]

        # Mark the end of the word
        node.is_end = True

    # Check if all prefixes of a word are present in the Trie
    def all_prefixes_exist(self, root, word):
        # Start from the root
        node = root

        # Check each character one by one
        for ch in word:
            # Move to the next character node
            node = node.children.get(ch)

            # If node is missing or prefix not marked as word end, return false
            if not node or not node.is_end:
                return False

        # All prefixes exist
        return True

    # Find the longest complete string
    def longest_complete_string(self, root, words):
        # Insert all words into the Trie
        for word in words:
            self.insert(root, word)

        ans = ""

        # Check each word to see if it's a complete string
        for word in words:
            if self.all_prefixes_exist(root, word):
                # Update if it's longer or lexicographically 
                # smaller than current answer
                if (len(word) > len(ans) or 
                (len(word) == len(ans) and word < ans)):
                    ans = word

        # If no valid complete string found, return "None"
        return ans if ans else "None"


# Driver code
if __name__ == "__main__":
    # Create the root of the Trie
    root = TrieNode()

    # Create a Solution object
    sol = Solution()

    # List of input words
    words = ["n", "ni", "nin", "ninj", "ninja", "ninga"]

    # Find and print the longest complete string
    print(sol.longest_complete_string(root, words))
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485