Getting list of unique substrings of a given string

Question

The task is to obtain a unique list of substrings in python.

I am currently using the breakup of the problem into 2 parts: obtain a list of all the substrings, followed by obtaining unique substrings.

I am using the below code:

substrings=[]
for i in range(0,len(inputstring)+1):
    for j in range(i+1,len(inputstring)+1):
        substr=inputstring[i:j]
        substrings.append(substr)
uniq=[]
for ss in substrings:
    if ss not in uniq:
        uniq.append(ss)

Is there a faster way to solve this problem or a so-called python way of doing it in a more flexible way?

a simple example string being: "aabaa", possible substrings are [a,a,b,a,a,aa,ab,ba,aa,aab,aba,baa,aaba,abaa,aabaa], unique substring which is desired at the end [a,b,aa,ab,ba,aab,aba,baa,aaba,abaa,aabaa]

Make uniq a set which will make the if ss not in uniq execute much faster. Also see Getting all combinations of a string and its substrings. — martineau
– martineau, Commented Jul 24, 2019 at 14:14
@Austin, I just edited the question to contain sample input and expected results — Ashwin Geet D'Sa
– Ashwin Geet D'Sa, Commented Jul 24, 2019 at 14:34

Pixel · Accepted Answer · 2019-08-12 16:49:43Z

1

Use Itertools and Set. Similar to the answer of Edwin but with Itertools, and in one line.

import itertools

uniq=list(set([inputstring[x:y] for x, y in itertools.combinations(
            range(len(inputstring) + 1), r = 2)]))

Basically you use itertools to first find all combinations, then set to find unique elements, then cast to list.

Code for combinations taken from https://www.geeksforgeeks.org/python-get-all-substrings-of-given-string/

Edit for a clearer explanation: First, use combinations to get all pair of indexes corresponding to substrings. The trick here is that itertools.combinations starts with all (0,X) pairs, and then (1,X) pairs, etc. Since we are using combinations and not permutations, we eliminate thus reverse substrings such as (1,0) since they will have been seen in the (0,X) enumerations.

Then simply use these with a list comprehension to get all substrings, use a set to find unique elements, and cast to a list.

Hope that helps

edited Aug 12, 2019 at 16:49

answered Jul 24, 2019 at 14:27

Pixel

1017 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Pixel Over a year ago

Yes, but if you use itertools with permutations it will also return subsets like (1,0), which is undesirable in this case. Since in combinations order doesn't matter, and due to the way itertools.combinations iterates (starts with all (0,X), then (1,X), etc), combinations here will correctly return all substring

Ashwin Geet D'Sa Over a year ago

combination order matters as the permuted combination need not be the substring

Pixel Over a year ago

I don't understand that sentence. I'll edit to explain the code more maybe that will help

AlexArmaStudio · Accepted Answer · 2024-11-11 08:26:24Z

0

Use a set instead of a list for the second part. Finding something in a list costs O(n) while in a set it costs O(1) and you don't have to check if its new. Sets won't add something if it is already in the list.

uniq=set()
for i in range(0,len(inputstring)+1):
    for j in range(i+1,len(inputstring)+1):
        substr=inputstring[i:j]
        uniq.add(substr)

edited Nov 11, 2024 at 8:26

AlexArmaStudio

235 bronze badges

answered Jul 24, 2019 at 14:21

Edwin Wallis

715 bronze badges

Collectives™ on Stack Overflow

Getting list of unique substrings of a given string

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related