We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Distinct Substrings in a String

Number: 1838

Difficulty: Medium

Paid? Yes

Companies: Uber, ServiceNow, Intuit, Dunzo

Problem Description

Given a string s, return the number of distinct substrings of s. A substring is defined as any continuous sequence of characters obtained by deleting any number (possibly zero) of characters from the front and back of s.

Key Insights

  • All possible substrings can be generated by considering each possible start and end index.
  • Utilizing a set (or hash set) ensures that duplicates are automatically filtered.
  • Even though generating all substrings has a nested loop, the maximum length of s (500) keeps the solution efficient for the problem constraints.
  • Advanced methods (like suffix trees, suffix arrays, or rolling hash) can optimize the process closer to O(n) time but are more complex to implement.

Space and Time Complexity

Time Complexity: O(n^2) in the context of iterating over all substring intervals (n is the length of s).
Space Complexity: O(n^2) in the worst case for storing all distinct substrings.

Solution

The solution involves iterating through every possible substring of s by using two nested loops: one for the start index and another for the end index. Each generated substring is added to a set which handles duplicate removals automatically. After the loops, the size of the set gives the number of distinct substrings.

Key Data Structures and Techniques:

  • Set/Hash Set: to store distinct substrings.
  • Nested Loop: to generate all possible substrings.
  • (Optional) Advanced techniques like rolling hash and suffix arrays can optimize the solution, but the simple approach is sufficient given the constraints.

Code Solutions

# Function to count distinct substrings in a string
def countDistinctSubstrings(s):
    # Initialize a set to store unique substrings
    unique_subs = set()
    n = len(s)
    # Loop over all possible starting indices
    for i in range(n):
        # Loop over all possible ending indices (non-inclusive)
        for j in range(i + 1, n + 1):
            # Add the current substring to the set
            unique_subs.add(s[i:j])
    # Return the count of unique substrings
    return len(unique_subs)

# Example usage:
s = "aabbaba"
print(countDistinctSubstrings(s))  # Expected output: 21
← Back to All Questions