Problem of the day
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]).
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.
1 <= T <= 5
1 <= |S| <= 10^3
‘S’ contains only lowercase English letters.
Time Limit: 1 sec
2
sds
abc
6
7
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”, “” }.
2
aa
abab
3
8
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”, “” }
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.
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 :
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).
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).