Number Of Distinct Substring

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
18 upvotes
Asked in companies
FacebookLinkedInCapegemini Consulting India Private Limited

Problem statement

Ninja has been given a string ‘WORD’ containing lowercase English alphabets having length ‘N’. Ninja wants to calculate the number of distinct substrings in the ‘WORD’.

For Example :

For ‘WORD’ = “abcd” and ‘N’ = 4 following are the 10 distinct substrings of ‘WORD’.
“abcd”, “abc”, “ab”, “a”, “bcd”, “bc”, “b”, “cd”, “c”, and “d”

Can you help the Ninja to find out the number of distinct substrings in the ‘WORD’?

Note :

If you are going to use variables with dynamic memory allocation then you need to release the memory associated with them at the end of your solution.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T' representing the number of test cases. Then the test cases follow.

The first line of each test case contains an integer ‘N’ representing the length of the string ‘WORD’.

The second line of each test case contains the string ‘WORD’.
Output Format : 
For each test case, print the number of distinct substrings in the ‘WORD’

The output for each test case is printed in a separate line.
Constraints : 
1 <= T <= 100
1 <= N <= 10 ^ 3
‘a’ <= WORD[i] <= ‘z’

Where ‘WORD[i]’ denotes the element at position ‘i’ in 'WORD'.

Time Limit: 1 sec
Sample Input 1 :
2
3
aaa
4
abab
Sample Output 1 :
3
7

Explanation For Sample Output 1 :

For the first test case :
Following are distinct substrings of the given string ‘WORD’.
“aaa”
“aa”   
“a”

For the second test case :
Following are distinct substrings of the given string ‘WORD’.
“abab”
“aba” 
“ab”
“a”
“bab”
“ba”
“b”
Sample Input 2 :
2
1
z
3
abc
Sample Output 2 :
1
6

Explanation For Sample Output 2:

For the first test case:
There is only one possible substring of the given string ‘WORD’ which is also distinct so the answer will be 1.

For the second test case :
Following are distinct substrings of the given string ‘WORD’.
“abc”
“ab”
“a”
“bc”
“b”
“c”
Hint

Can you think of a solution by traversing through each substring?

Approaches (2)
Brute Force

The basic idea behind this approach is to use a HashSet ‘ans’ to store all the possible substrings generated from the string ‘WORD’. Finally, we return the size of the HashSet.

 

Here is the complete algorithm:

 

  1. Declare a HashSet ‘ans’ in which we store all distinct substrings.
  2. Run a loop for ‘i’ = 0 to less than the size of string ‘WORD’:
    • Declare an empty string ‘tempStr’ in which store substring of the string.
    • Run a loop for ‘j’ = ‘i’ to less than the size of string ‘WORD’:
      • Add ‘WORD[j]’ to ‘tempStr’.
      • Add this ‘tempStr’ to HashSet ‘ans’.
  3. Finally, return the size of ‘ans’.
Time Complexity

O(N ^ 3), where ‘N’ is the length of the string ‘WORD’.

 

First, we are generating all the possible substrings of ‘WORD’ it takes O(N^2) time, and then we are adding this substring into HashSet ‘ans', it takes O(N) time. Hence overall time complexity will be O(N ^ 3).

Space Complexity

O(N ^ 2), where ‘N’ is the length of the string ‘WORD’.

 

Because in the worst case the size of our hash set is of order ‘N ^ 2’ . Hence overall time complexity will be O(N ^ 2).

Code Solution
(100% EXP penalty)
Number Of Distinct Substring
Full screen
Console