Number Of Distinct Substring

Posted: 16 Apr, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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’.
Try Problem