Problem Description

Given a string s, you need to find and return the total number of distinct (unique) substrings that can be formed from it.

A substring is a contiguous sequence of characters within the string. You can obtain a substring by removing any number of characters (including zero) from the beginning of the string and any number of characters (including zero) from the end of the string.

For example, if s = "abc", the possible substrings are:

• Length 1: "a", "b", "c"
• Length 2: "ab", "bc"
• Length 3: "abc"

All these substrings are distinct, so the answer would be 6.

The solution uses a brute force approach by generating all possible substrings using nested loops. The outer loop i represents the starting position of the substring, and the inner loop j represents the ending position (exclusive). By using s[i:j] for all valid combinations of i and j where 0 ≤ i < j ≤ n, we generate all possible substrings. These substrings are stored in a set, which automatically handles duplicates, keeping only distinct values. The final answer is the size of this set, representing the count of distinct substrings.

Intuition

When we need to count distinct substrings, the key insight is that we need to examine every possible substring and keep track of which ones we've seen before. Since a substring is defined by its starting and ending positions in the original string, we can systematically generate all possibilities.

Think of it this way: for a string of length n, each substring can be uniquely identified by two things:

1. Where it starts (position i)
2. Where it ends (position j)

This naturally leads us to use two nested loops - one to fix the starting position and another to extend the ending position. For each starting position i, we can create substrings ending at positions i+1, i+2, ... up to n.

The challenge is handling duplicates. For instance, in the string "aaa", the substring "a" appears at multiple positions, but we should count it only once. This is where Python's set data structure becomes perfect - it automatically handles uniqueness for us. By adding each substring s[i:j] to a set, duplicate substrings are ignored, and we're left with only the distinct ones.

The beauty of this approach is its simplicity: generate all substrings using slice notation s[i:j], let the set handle deduplication, and return the size of the set. While this may not be the most efficient solution for very long strings, it's straightforward to understand and implement, making it an excellent starting point for solving this problem.

Learn more about Trie patterns.

Solution Approach

The solution uses a brute force enumeration strategy to find all distinct substrings. Let's walk through the implementation step by step:

1. Get the string length: First, we store the length of the input string s in variable n for convenience.

2. Generate all substrings using nested loops: The core of the solution uses a set comprehension with two nested loops:

   • The outer loop: for i in range(n) iterates through all possible starting positions (from index 0 to n-1)
   • The inner loop: for j in range(i + 1, n + 1) iterates through all possible ending positions for each starting position i
   • The range (i + 1, n + 1) ensures that:
     • j is always greater than i (so we get valid substrings)
     • j can go up to n (to include substrings that end at the last character)

3. Extract substrings using slicing: For each pair of (i, j), we extract the substring using Python's slice notation s[i:j]. This gives us the substring starting at index i and ending at index j-1.

4. Use a set for automatic deduplication: All generated substrings are placed in a set using the set comprehension {s[i:j] for i in range(n) for j in range(i + 1, n + 1)}. The set data structure automatically handles duplicate removal - if the same substring appears multiple times, it's only stored once.

5. Return the count: Finally, we use len() to get the size of the set, which gives us the count of distinct substrings.

Time Complexity: O(n²) for generating all substrings, where each substring extraction takes O(n) time in the worst case, leading to overall O(n³).

Space Complexity: O(n²) in the worst case when all substrings are distinct, as we need to store them in the set.

Example Walkthrough

Let's walk through the solution with the string s = "aba".

Step 1: Initialize

• String: s = "aba"
• Length: n = 3

Step 2: Generate all substrings using nested loops

We'll systematically generate substrings by fixing a starting position i and varying the ending position j:

• When i = 0 (starting from 'a' at index 0):

  • j = 1: s[0:1] = "a"
  • j = 2: s[0:2] = "ab"
  • j = 3: s[0:3] = "aba"

• When i = 1 (starting from 'b' at index 1):

  • j = 2: s[1:2] = "b"
  • j = 3: s[1:3] = "ba"

• When i = 2 (starting from 'a' at index 2):

  • j = 3: s[2:3] = "a"

Step 3: Collect in a set

All generated substrings: ["a", "ab", "aba", "b", "ba", "a"]

When we add these to a set, the duplicate "a" (which appears twice - once from position 0 and once from position 2) is automatically removed.

Final set: {"a", "ab", "aba", "b", "ba"}

Step 4: Count distinct substrings

The set contains 5 distinct substrings, so the answer is 5.

This example demonstrates how the nested loops generate all possible substrings and how the set automatically handles deduplication when we encounter the same substring at different positions.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n^3)

The code uses nested loops to generate all possible substrings. The outer loop runs n times (for each starting position i), and the inner loop runs up to n times for each i (for each ending position j). This gives us O(n^2) substring generations. However, each substring extraction s[i:j] takes O(j-i) time, which in the worst case is O(n). Additionally, adding each substring to the set requires hashing, which takes O(length of substring), also up to O(n) in the worst case. Therefore, the overall time complexity is O(n^2) * O(n) = O(n^3).

Space Complexity: O(n^2)

The set stores all distinct substrings. In the worst case where all characters are unique, the number of distinct substrings is n * (n + 1) / 2, which is O(n^2). Each substring can have a maximum length of n, so theoretically the total space for storing all substrings could be O(n^3). However, since the problem typically considers the space complexity in terms of the number of distinct elements stored rather than their total size, and given the reference answer, the space complexity is O(n^2).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in the Inner Loop Range

One of the most common mistakes is incorrectly setting the range for the inner loop j. Developers often write:

Incorrect:

distinct_substrings = {s[i:j] for i in range(n) for j in range(i, n)}

Why it's wrong:

• When j = i, the slice s[i:i] produces an empty string "", which is not a valid substring
• When j = n-1, we miss substrings that include the last character

Correct approach:

distinct_substrings = {s[i:j] for i in range(n) for j in range(i + 1, n + 1)}

• i + 1 ensures we skip empty strings (substring must have at least one character)
• n + 1 ensures we include substrings ending at the last character (since Python slicing is exclusive of the end index)

2. Using a List Instead of a Set

Incorrect:

distinct_substrings = [s[i:j] for i in range(n) for j in range(i + 1, n + 1)]
return len(distinct_substrings)

Why it's wrong: Lists don't automatically remove duplicates. If the string has repeating patterns (like "aab"), the substring "a" appears twice, and using a list would count it twice.

Solution: Always use a set to automatically handle deduplication:

distinct_substrings = {s[i:j] for i in range(n) for j in range(i + 1, n + 1)}

3. Memory Issues with Very Long Strings

For strings with length approaching 10^4 or more, storing all substrings can cause memory issues since there are O(n²) possible substrings.

Alternative approach for memory-constrained scenarios:

def countDistinct(self, s: str) -> int:
    n = len(s)
    distinct_substrings = set()
  
    for i in range(n):
        for j in range(i + 1, n + 1):
            distinct_substrings.add(s[i:j])
          
    return len(distinct_substrings)

While this doesn't fundamentally reduce memory usage, it allows for potential optimizations like:

• Early termination if a memory limit is reached
• Batch processing of substrings
• Using a more memory-efficient data structure like a Trie for very large inputs

4. Forgetting Edge Cases

Developers sometimes forget to handle edge cases properly:

Edge cases to consider:

• Empty string: s = "" should return 0
• Single character: s = "a" should return 1
• All same characters: s = "aaaa" has only 4 distinct substrings: "a", "aa", "aaa", "aaaa"

Robust solution:

def countDistinct(self, s: str) -> int:
    if not s:  # Handle empty string
        return 0
      
    n = len(s)
    distinct_substrings = {s[i:j] for i in range(n) for j in range(i + 1, n + 1)}
    return len(distinct_substrings)