DEV Community 👩‍💻👨‍💻

Omkar Bhagat
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']
Enter fullscreen mode Exit fullscreen mode

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)
        res.add(s)

        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']
Enter fullscreen mode Exit fullscreen mode

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

        res.add(s)

        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']
Enter fullscreen mode Exit fullscreen mode

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).

Tree diagram for substrings

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! :)

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.