DEV Community 👩‍💻👨‍💻 is a community of 967,611 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Omkar Bhagat

Posted on • Updated on

Finding Unique Substrings In A Given String

Given a string `abc`, our goal is to generate the following unique substrings:

``````['abc', 'bc', 'ab', 'c', 'b', 'a']
``````

With A Queue

We can do it with the help of a queue.

Here's the logic:

1. Take the given string, add it to our queue `q`.
2. While the `q` is not empty, repeat steps 3-5.
3. Pop the first item in the `q`.
4. Add this to our final result list called `res`.
5. Add left substring (e.g. `ab`) and right substring (e.g. `bc`) to the queue only if it isn't already in `res`.
6. Once queue is empty, print `res`.
``````def findSubstrings(s):

res = set()
q = [s]

while q:

s = q.pop(0)

x = 0
y = len(s)-1

right_string = s[x+1:y+1]
left_string = s[x:y]

if right_string and right_string not in res:
q.append(right_string)

if left_string and left_string not in res:
q.append(left_string)

return res

r = list(findSubstrings('abc'))
r.sort(key=len, reverse=True)
print(r)

# Result:
# ['abc', 'ab', 'bc', 'b', 'c', 'a']
``````

With Recursion

Here the logic is the same but we do it recursively using one helper function.

``````def findSubstrings(s):

res = set()

def helper(s):

if len(s) <= 0:
return

right_string = s[1:len(s)]
left_string = s[0:len(s)-1]

if right_string not in res:
helper(right_string)

if left_string not in res:
helper(left_string)

helper(s)

return res

r = list(findSubstrings('abc'))
r.sort(key=len, reverse=True)
print(r)

# Result:
# ['abc', 'ab', 'bc', 'b', 'c', 'a']
``````

Complexity

I guess the worst case time here could be `(2^n)-1` if we don't use a set to check for unique values (where n is length of the given string).

Final Thoughts

Where can you use this? Once you understand the basic logic, you can use it to solve many string related problems. For example: Finding the longest palindromic substring.

There could be various other (simpler) ways to achieve this but I believe this approach helps us visualize the process. Thanks for reading! :)