1 def remove_prefixes(words):
 2     if not words:
 3         return []
 4 
 5     # 1. Sort words lexicographically to bring prefixes next to their parents
 6     # This takes O(N log N * L) where L is max string length
 7     sorted_words = sorted(words)
 8     prefixes_to_remove = set()
 9 
10     for i in range(len(sorted_words) - 1):
11         current_word = sorted_words[i]
12         next_word = sorted_words[i+1]
13         
14         # 2. Check if the current word is a prefix of the next word
15         # .startswith() handles the prefix check efficiently
16         if next_word.startswith(current_word):
17             prefixes_to_remove.add(current_word)
18 
19     # 3. Filter the original list to maintain relative order
20     return [w for w in words if w not in prefixes_to_remove]
21 
22 # Example usage:
23 words1 = ["a", "abc", "abc hello", "bc"]
24 print(remove_prefixes(words1))  # Output: ["abc hello", "bc"]
25 
26 words2 = ["a", "ab", "abc"]
27 print(remove_prefixes(words2))  # Output: ["abc"]

 1 class TrieNode:
 2     def __init__(self):
 3         self.children = {}
 4         self.is_end = False
 5 
 6 class Trie:
 7     def __init__(self):
 8         self.root = TrieNode()
 9 
10     def insert(self, word):
11         node = self.root
12         for char in word:
13             if char not in node.children:
14                 node.children[char] = TrieNode()
15             node = node.children[char]
16         node.is_end = True
17 
18     def is_prefix_of_others(self, word):
19         node = self.root
20         for char in word:
21             node = node.children[char]
22         # If the node where the word ends has children, 
23         # it means this word is a prefix of a longer string.
24         return len(node.children) > 0
25 
26 def remove_prefixes_trie(words):
27     trie = Trie()
28     
29     # 1. Build the Trie
30     for word in words:
31         trie.insert(word)
32     
33     # 2. Filter words based on whether they have children in the Trie
34     # This maintains the original relative order
35     result = []
36     for word in words:
37         if not trie.is_prefix_of_others(word):
38             result.append(word)
39             
40     return result
41 
42 # Test
43 words = ["a", "abc", "abc hello", "bc"]
44 print(remove_prefixes_trie(words)) # Output: ["abc hello", "bc"]