Problem title
Difficulty
Avg time to solve

Fibonacci Sum
Moderate
15 mins
Create Array
Easy
15 mins
Divide Chocolates
Moderate
30 mins
Number Of Distinct Substring
Moderate
30 mins
Best Meeting Point
Easy
15 mins
Disconnect the ‘GRID’ by removing the minimum number of cities
Hard
10 mins
Round Robin Scheduling
Easy
15 mins
Network Delay Time
Easy
20 mins
Infix To Postfix
Easy
20 mins
My Calendar III
Easy
10 mins
5

Number Of Distinct Substring

Difficulty: MEDIUM
Contributed By
Avg. time to solve
30 min
Success Rate
70%

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.
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”
Reset Code
Full screen
copy-code
Console