Count Distinct Substrings

Practice Link

Given a string 'S', you are supposed to return the number of distinct substrings(including empty substring) of the given string. You should implement the program using a trie.

Using Trie#

Every substring of S is a prefix of some suffix of S. So by inserting all suffixes of S into a Trie, we naturally enumerate all distinct substrings — each new Trie node created during an insertion corresponds to exactly one new distinct substring not seen before. The count of newly created nodes across all suffix insertions equals the number of distinct non-empty substrings. Adding 1 accounts for the empty substring.

• Insert all suffixes of S into the Trie, starting from index i = 0, 1, ..., n-1.
• The insert function returns the number of new nodes created (characters not previously seen in this path).
• Sum the new-node counts across all suffix insertions and add 1 (for the empty substring).

class TrieNode {
public:
    TrieNode* children[26];
    TrieNode(){
        for(int i=0;i<26;i++)
            children[i] = NULL;
    }

};

class Trie{
    public:
    TrieNode* root;
    Trie(){
        root=new TrieNode();
    }
 
    int insert(string& str){
        int newNode=0;
        TrieNode* curr=root;
        for(char ch: str){
            int idx=ch-'a';
            if(curr->children[idx]==nullptr){
                curr->children[idx]=new TrieNode();
                newNode++;
            }
            curr=curr->children[idx];
        }
        return newNode;
 
    }
};

int countDistinctSubstrings(string &s)
{
    Trie trie;
    int count =0;
    for(int i=0;i<s.size();i++)
    {
        string suffix = s.substr(i);
        count += trie.insert(suffix);
    }
    return count+1;
}

Time Complexity: O(n^2)

Space Complexity: O(n^2)