Count Distinct Substrings 🎯

Welcome to our deep dive into Data Structures and Algorithms! Today, we're going to explore a fascinating problem: Counting Distinct Substrings. This lesson is designed for both beginners and intermediate learners, so let's get started! 🎉

What are Substrings? 📝

A substring is a contiguous sequence of characters within a string. For example, in the string "Hello, World!", substrings could be "Hello", "llo", "World", or even "o".

Why Count Distinct Substrings? 💡

Counting distinct substrings can be useful in various real-world scenarios, such as text analysis, bioinformatics, and computer security. It helps us understand the unique patterns within a given text.

Solving the Problem 🔧

We'll use a hash map (or dictionary in some languages) to solve this problem. Here's why:

Hash maps allow us to store and quickly access key-value pairs. In this case, the keys are substrings, and the values are the number of times each substring appears.
Since we're only interested in distinct substrings, we can count the number of unique keys (substrings) in our hash map at the end.

Let's dive into a practical example!

Practical Example 💻

Let's count the distinct substrings in the string "banana".

python

def count_distinct_substrings(s):
    substrings = set()  # Using a set to store unique substrings

    for i in range(len(s)):  # Iterate through the string
        for j in range(i, len(s)):  # Iterate through substrings starting from i
            substrings.add(s[i:j+1])  # Add substring to the set

    return len(substrings)  # Return the number of unique substrings

print(count_distinct_substrings("banana"))  # Output: 6

In the above example, we created a function count_distinct_substrings that generates all substrings of the input string and counts the unique ones using a set.

Advanced Example 🔝

Let's count the distinct substrings in the string "A man, a plan, a canal: Panama!".

python

print(count_distinct_substrings("A man, a plan, a canal: Panama!"))  # Output: 62

In this example, we used a larger, more complex string to demonstrate the versatility of our solution.

Quiz Time! 🕹️

Remember, understanding Data Structures and Algorithms is a journey, and the more you practice, the better you'll get! Keep exploring and learning with CodeYourCraft. 🚀

Happy coding! 🖖️