Count Distinct Substrings

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
180 upvotes
Asked in companies
Paytm (One97 Communications Limited)AdobeAmazon

Problem statement

Given a string 'S', you are supposed to return the number of distinct substrings(including empty substring) of the given string. You should implement the program using a trie.

Note :
A string ‘B’ is a substring of a string ‘A’ if ‘B’ that can be obtained by deletion of, several characters(possibly none) from the start of ‘A’ and several characters(possibly none) from the end of ‘A’. 

Two strings ‘X’ and ‘Y’ are considered different if there is at least one index ‘i’  such that the character of ‘X’ at index ‘i’ is different from the character of ‘Y’ at index ‘i’(X[i]!=Y[i]).
Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains a single integer ‘T’ denoting the number of test cases.

Then, the ‘T’ test cases follow.

The first line of each test case contains a string.
Output Format :
For each test case, print an integer denoting the number of distinct substrings in the given string.

The output for each test case will be printed in a separate line.
Note :
You don’t need to print anything, It has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= |S| <= 10^3

‘S’ contains only lowercase English letters.

Time Limit: 1 sec
Sample Input 1 :
2
sds
abc
Sample Output 1 :
6
7
Explanation of Sample Input 1 :
In the first test case, the 6 distinct substrings are { ‘s’,’ d’, ”sd”, ”ds”, ”sds”, “” }

In the second test case, the 7 distinct substrings are {‘a’, ‘b’, ‘c’, “ab”, “bc”, “abc”, “” }.
Sample Input 2 :
2
aa
abab
Sample Output 2 :
3
8
Explanation of Sample Input 2 :
In the first test case, the two distinct substrings are {‘a’, “aa”, “” }.

In the second test case, the seven distinct substrings are {‘a’, ‘b’, “ab”, “ba”, “aba”, “bab”, “abab”, “” }


Hints:
1. Can you think about a data structure that can be used to store the distinct substrings?
2. Can you think about using the fact that every substring of ‘S’ is a prefix of some suffix string of ‘S’?
3. Try to insert every suffix of the string in Trie.
Approaches (3)
HashSet based Approach

The idea is to find all substrings and insert each substring into a HashSet. Since there will be no duplicates possible into the HashSet, after we have inserted all the substrings in the HashSet the size of the HashSet will be equal to the number of distinct substrings.

 

The steps are as follows :

  1. Iterate through the current string and pivot each index, let’s say the pivoted index is ‘i’.
    • Iterate from the ‘i’ till the end of the loop, let’s say the current index is ‘j’.
      • Insert the substring from index ‘i’ to index ‘j’ into the HashSet.
  2. Return the size of the HashSet+1(extra 1 for empty substring), as that will be the number of distinct substrings in the given string.
Time Complexity

O(N^3), where N is the length of the given string.

 

We are iterating through the given string and pivoting each element. There will be N elements to pivot and for each pivot, we are iterating till the end of the string and inserting each substring into the HashSet. Calculating the substring will take O(N) time. Also, the insert operations in the HashSet will take time equal to the length of the string being inserted. Thus, the total time complexity will be O(N^3).

Space Complexity

O(N^2), where N is the length of the given string.

 

We are inserting each substring into the HashSet. So in the worst case when all the characters in the string are distinct, there will be N^2 strings in the HashSet. Thus, the overall space complexity will be O(N^2).

Code Solution
(100% EXP penalty)
Count Distinct Substrings
Full screen
Console