Return string that is not a substring of other strings - is it possible in time less than O(n^2)?
<p>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 - <code>['abc','abcd','ab','def','efgd']</code>.
Output should be - <code>'abcd'</code> and <code>'efgd'</code>
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:</p>

<pre><code>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'])                  
</code></pre>

<p>Pop the first element.  Go through each remaining element and see if the shorter string is a substring of the longer string.  Repeat.  That should be O(n log n)</p>

<p>EDIT: Rough draft of implementation</p>

<pre><code>def not_substrings(l):
    mask = [True]*len(l)
    for i in range(len(l)):
        if not mask[i]:
            continue
        for j in range(i+1, len(l)):
            if len(l[i]) &gt; len(l[j]):
                if l[j] in l[i]:
                    mask[j] = False
            elif l[j] == l[i]:
                mask[j] = False
                mask[i] = False
            else:
                if l[i] in l[j]:
                    mask[i] = False
        if mask[i]:
            print l[i]
</code></pre>

<p>I haven't run this code, but it should be roughly correct.  I don't know if there's a way of doing this without the mask, or what time complexity the <code>[True]*len(l)</code> statement has.  I haven't done any rigorous analysis, but this looks <code>n log n</code> to me, because each iteration only iterates over the remainer of the list, not the entire list.</p>

python string python-2.7 substring