 New update is available. Click here to update.
Last Updated: 16 Apr, 2021

# Number Of Distinct Substring

Moderate   ## Problem statement #### 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”
``````

#### 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
`````` ## Approaches

### 01 Approach 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’: 