1698-Number of Distinct Substrings in a String Using Trie

Problem Statement

Problem Statement: Given a string of alphabetic characters. Return the count of distinct substrings of the string(including the empty string) using the Trie data structure.

Examples:

Example 1:
Input:
 S1= “ababa”
Output: Total number of distinct substrings : 10
Explanation: All the substrings of the string are a, ab, aba, abab, ababa, b, ba, bab, baba, a, ab, aba, b, ba, a. Many of the substrings are duplicated. The distinct substrings are a, ab, aba, abab, ababa, b, ba, bab, baba. Total Count of the distinct substrings is 9 + 1(for empty string) = 10.



Example 2:
Input:
 S1= “ccfdf”

Output: Total number of distinct substrings : 14
Explanation:
All the substrings of the string are c, cc, ccf, ccfd, ccfdf, c, cf, cfd, cfdf, f, fd, fdf, d, df, f. Many of the substrings are duplicated. The distinct substrings are c, cc, ccf, ccfd, ccfdf, cf, cfd, cfdf, f, fd, fdf, d, df. Total Count of the distinct substrings is 13 + 1(for empty string) = 14.

Intuition

Approach 1:

Brute- Generate all substrings in N^2 and put in set to make unique 
N^2 logn 

optimal- Insert in trie, and it will eliminate the duplicate strings

Video Links

Approach 1:

C++

class Node{
public:
    Node *links[26];
};

class Solution{
public:
    Node *root ;
    Solution(){
        root = new Node();
    }

    int find_subs(string s){
        Node *temp = root;
        int count = 0;
        for(int i=0; i<s.size(); i++){
            for(int j=i; j<s.size(); j++){
                char ch = s[j];
                if(temp->links[ch - 'a'] == nullptr){
                    count++;
                    temp->links[ch - 'a'] = new Node();
                }
                temp = temp->links[ch-'a'];
            }
        }

        return count;
    }
};

Approach 2:

C++

Approach 3:

C++

Approach 4:

C++