Return string that is not a substring of other strings - is it possible in time less than O(n^2)?
Question: You are given an array of strings. you have to return only those strings that
are not sub strings of other strings in the array. Input -
`['abc','abcd','ab','def','efgd']`. Output should be - `'abcd'` and `'efgd'` I
have come up with a solution in python that has time complexity O(n^2). Is
there a possible solution that gives a lesser time complexity? My solution:

    
    
    def sub(l,s):
      l1=l
      for i in range (len(l)):
            l1[i]=''.join(sorted(l1[i]))
      for i in l1:      
             if s in i:
                  return True
      return False
    
    def main(l):
          for i in range(len(l)):
                if sub(l[0:i-1]+l[i+1:],l[i])==False:
                      print l[i]
    
    
    main(['abc','abcd','ab','def','efgd'])                  
    


Answer: Is memory an issue? You could turn to the tried and true...TRIE!

Build a suffix tree!

Given your input `['abc','abcd','ab','def','efgd']`

We would have a tree of

    
    
                  _
                / | \
               a  e  d
              /   |   \
             b*   f    e
            /     |     \
           c*     g      f*
          /       |
         d*       d*
    

Utilizing a DFS (Depth-First-Search) search of said tree you would locate the
deepest leafs `abcd`, `efgd`, and `def`

Tree traversal is pretty straight forward and your time complexity is
`O(n*m).` A much better improvement over the `O(n^2)` time you had previously.

With this approach it becomes simple to add new keys and still make it easy to
find the unique keys.

Consider adding the key `deg`

your new tree would be approximately

    
    
                  _
                / | \
               a  e  d
              /   |   \
             b*   f    e
            /     |   / \
           c*     g  g*   f*
          /       |
         d*       d*
    

With this new tree it is still a simple matter of performing a DFS search to
obtain the unique keys that are not prefixes of others.

    
    
    from typing import List
    
    
    class Trie(object):
        class Leaf(object):
            def __init__(self, data, is_key):
                self.data = data
                self.is_key = is_key
                self.children = []
    
            def __str__(self):
                return "{}{}".format(self.data, "*" if self.is_key else "")
    
        def __init__(self, keys):
            self.root = Trie.Leaf('', False)
            for key in keys:
                self.add_key(key)
    
        def add_key(self, key):
            self._add(key, self.root.children)
    
        def has_suffix(self, suffix):
            leaf = self._find(suffix, self.root.children)
    
            if not leaf:
                return False
    
            # This is only a suffix if the returned leaf has children and itself is not a key
            if not leaf.is_key and leaf.children:
                return True
    
            return False
    
        def includes_key(self, key):
            leaf = self._find(key, self.root.children)
    
            if not leaf:
                return False
    
            return leaf.is_key
    
        def delete(self, key):
            """
            If the key is present as a unique key as in it does not have any children nor are any of its nodes comprised of
             we should delete all of the nodes up to the root
            If the key is a prefix of another long key in the trie, umark the leaf node
            if the key is present in the trie and contains no children but contains nodes that are keys we should delete all
             nodes up to the first encountered key
            :param key:
            :return:
            """
    
            if not key:
                raise KeyError
    
            self._delete(key, self.root.children, None)
    
        def _delete(self, key, children: List[Leaf], parents: (List[Leaf], None), key_idx=0, parent_key=False):
            if not parents:
                parents = [self.root]
    
            if key_idx >= len(key):
                return
    
            key_end = True if len(key) == key_idx + 1 else False
            suffix = key[key_idx]
            for leaf in children:
                if leaf.data == suffix:
                    # we have encountered a leaf node that is a key we can't delete these
                    # this means our key shares a common branch
                    if leaf.is_key:
                        parent_key = True
    
                    if key_end and leaf.children:
                        # We've encountered another key along the way
                        if parent_key:
                            leaf.is_key = False
                        else:
                            # delete all nodes recursively up to the top of the first node that has multiple children
                            self._clean_parents(key, key_idx, parents)
                    elif key_end and not leaf.children:
                        # delete all nodes recursively up to the top of the first node that has multiple children
                        self._clean_parents(key, key_idx, parents)
    
                    # Not at the key end so we need to keep traversing the tree down
                    parents.append(leaf)
                    self._delete(key, leaf.children, parents, key_idx + 1, key_end)
    
        def _clean_parents(self, key, key_idx, parents):
            stop = False
            while parents and not stop:
                p = parents.pop()
    
                # Need to stop processing a removal at a branch
                if len(p.children) > 1:
                    stop = True
    
                # Locate our branch and kill its children
                for i in range(len(p.children)):
                    if p.children[i].data == key[key_idx]:
                        p.children.pop(i)
                        break
                key_idx -= 1
    
        def _find(self, key, children: List[Leaf]):
            if not key:
                raise KeyError
    
            match = False
            if len(key) == 1:
                match = True
    
            suffix = key[0]
            for leaf in children:
                if leaf.data == suffix and not match:
                    return self._find(key[1:], leaf.children)
                elif leaf.data == suffix and match:
                    return leaf
            return None
    
        def _add(self, key, children: List[Leaf]):
            if not key:
                return
    
            is_key = False
            if len(key) == 1:
                is_key = True
    
            suffix = key[0]
            for leaf in children:
                if leaf.data == suffix:
                    self._add(key[1:], leaf.children)
                    break
            else:
                children.append(Trie.Leaf(suffix, is_key))
                self._add(key[1:], children[-1].children)
    
            return
    
        @staticmethod
        def _has_children(leaf):
            return bool(leaf.children)
    
    
    def main():
        keys = ['ba', 'bag', 'a', 'abc', 'abcd', 'abd', 'xyz']
        trie = Trie(keys)
        print(trie.includes_key('ba'))  # True
        print(trie.includes_key('b'))  # False
        print(trie.includes_key('dog'))  # False
        print(trie.has_suffix('b'))  # True
        print(trie.has_suffix('ab'))  # True
        print(trie.has_suffix('abd'))   # False
    
        trie.delete('abd')  # Should only remove the d
        trie.delete('a')    # should unmark a as a key
        trie.delete('ba')   # should remove the ba trie
        trie.delete('xyz')  # Should remove the entire branch
        trie.delete('bag')  # should only remove the g
    
        print(trie)
    
    if __name__ == "__main__":
        main()
    

Please note the above trie implementation does not have a DFS search
implemented; however, provides you with some amazing legwork to get started.

