Python: Removing longer substrings of a string within a set

Question

I have a long string. Of this string I have created a large set of substrings where each element may be a sub-substring of some other substring within the set. I am attempting to create a set of only the shortest substrings from my original set. Here is my attempt at a solution so far.

string = 'ABAAABAAB'
setA = {'ABAAAB', 'BAAAB', 'AAAB', 'AAB'}
setB = setA.copy()
setC = setA.copy()
for s1 in setA:
    len1 = len(s1)
    for s2 in setB:
        len2 = len(s2)
        if s1 in s2 and len2 > len1:
            setC.discard(s2)

I am creating a copy of my original set and iterating through the elements of setA then setB. If one of those elements is a substring of the other element, I discard the longer element. The runtime of my solution increases greatly as the elements of setA increase due to use of nested loops. Is there a solution with lower time complexity?

Answer 1

You can iterate through setA from the shortest string to the longest, and add a given string to setC only if none of the possible substrings of the string is already in setC. You can generate all possible substrings from a string by iterating a starting index through the length of the string, and iterating the size of the substring from 1 to the remaining length of the string from the current starting index, and then using the starting index and the substring length to slice the string:

setC = set()
for s in sorted(setA, key=len):
    if not any(s[i: i + n + 1] in setC for i in range(len(s)) for n in range(len(s) - i)):
        setC.add(s)

setC becomes:

{'AAB'}

This improves the overall time complexity from O(n^2) of your solution to O(n log n).

Answer 2

To make the substring searching algorithm @blhsing posted a little easier to read, you can just separate out the steps into their own loops. This is the same logic just not inside one line.

setC = set()
sortedList = sorted(setA, key=len)
for substring in sortedList:
    if not substring_in_set(substring, set3):
        setC.add(substring)


# Checks whether the subtrings is in the set 
# and returns True or False
def substring_in_set(substring, set):
    for i in range(len(substring)):
        for n in range(len(substring) - i):
            if substring[i: i + n + 1] in set:
                return True
    return False