Number Of Distinct Substring

Moderate

Solve now

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

Solve now

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:

Declare a HashSet ‘ans’ in which we store all distinct substrings.
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’.
Finally, return the size of ‘ans’.

Solve now

02 Approach

The basic idea of this approach is the first iterate over this string ‘WORD’ and store all substrings of this string into a ‘TRIE’. Then iterate through this ‘TRIE’ and count how many words are there in the ‘TRIE’ that is our desired result.

The steps are as follows:

Declare a variable ‘count’ = 0 in which we store the number of the distinct substrings in the string ‘WORD’.
TrieNode class/struct:
- Make an array of ‘children’ that is a type of class/struct TrieNode.
- Make a node ‘trie’ of the class/struct TrieNode.
- We run a loop ‘i’ = 0 to ‘N’:
  - Call insertIntoTrie(substring(i)).
- Call countNodeInTrie(‘trie’).
- Finally, return ‘count’.
insertIntoTrie(‘word’)
- Make a TrieNode ‘curr’ and store ‘trie’.
- Run a loop for ‘i’ = 0 to the length of the ‘word’:
  - ‘Index’ = ‘word[i]’ - ‘a’.
  - If ‘curr.children[‘index’]’ is equal to ‘NULL’:
    - Add a new ‘TrieNode’ node at this ’curr’ node.
  - ‘curr’ is equal to ‘curr.children[index]'.
countNodeInTrie(‘curr’).
- If ‘curr’ is equal to ‘NULL’:
  - Return.
- Run a loop ‘i’ to 26:
  - If ‘curr.children[i]’ is not equal to ‘NULL’:
    - ‘count’ = ‘count’ +1
  - ‘countNodeInTrie’(‘curr.children[i]’).