Count distinct substrings
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.

Note :

A string ‘B’ is a substring of a string ‘A’ if ‘B’ that can be obtained by deletion of, several characters(possibly none) from the start of ‘A’ and several characters(possibly none) from the end of ‘A’. Two strings ‘X’ and ‘Y’ are considered different if there is at least one index ‘i’ such that the character of ‘X’ at index ‘i’ is different from the character of ‘Y’ at index ‘i’(X[i]!=Y[i]).

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases. Then, the ‘T’ test cases follow. The first line of each test case contains a string.

Output Format :

For each test case, print an integer denoting the number of distinct substrings in the given string. The output for each test case will be printed in a separate line.

Note :

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints :

1

Question

Count distinct substrings

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.

Note :

A string ‘B’ is a substring of a string ‘A’ if ‘B’ that can be obtained by deletion of, several characters(possibly none) from the start of ‘A’ and several characters(possibly none) from the end of ‘A’. 

Two strings ‘X’ and ‘Y’ are considered different if there is at least one index ‘i’  such that the character of ‘X’ at index ‘i’ is different from the character of ‘Y’ at index ‘i’(X[i]!=Y[i]).

Input Format :

The first line contains a single integer ‘T’ denoting the number of test cases.

Then, the ‘T’ test cases follow.

The first line of each test case contains a string.

Output Format :

For each test case, print an integer denoting the number of distinct substrings in the given string.

The output for each test case will be printed in a separate line.

Note :

You don’t need to print anything, It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= |S| <= 10^3

‘S’ contains only lowercase English letters.

Time Limit: 1 sec

Accepted Answer

Step 1 : I used something similar to sliding window algorithm
Step 2 : I called a function which contains starting index of the string , an empty StringBuilder as it is mutable and an Arraylist to store indexes of all valid substrings as parameters.
Step 3 : declared a base case which states that the whole string is traversed.
Step 4 : declared some conditions,
(a) if the output String does not matches the length of the substring then append the character in output string (here output string is the StringBuilder we passed as parameter).
(b) if the length of output String got matched with given substring then compare the output string with substring.
if its matches then calculate its starting index and add it in the list.
and lastly remove first character from output string and add character at current index in output string and call the function recursively to check all the occurrences.

Accepted Answer

HashSet based Approach

The idea is to find all substrings and insert each substring into a HashSet. Since there will be no duplicates possible into the HashSet, after we have inserted all the substrings in the HashSet the size of the HashSet will be equal to the number of distinct substrings.

The steps are as follows :

Iterate through the current string and pivot each index, let’s say the pivoted index is ‘i’.
- Iterate from the ‘i’ till the end of the loop, let’s say the current index is ‘j’.
  - Insert the substring from index ‘i’ to index ‘j’ into the HashSet.
Return the size of the HashSet+1(extra 1 for empty substring), as that will be the number of distinct substrings in the given string.

Space Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the given string.

We are inserting each substring into the HashSet. So in the worst case when all the characters in the string are distinct, there will be N^2 strings in the HashSet. Thus, the overall space complexity will be O(N^2).

Time Complexity: O(n^3)Explanation:

O(N^3), where N is the length of the given string.

We are iterating through the given string and pivoting each element. There will be N elements to pivot and for each pivot, we are iterating till the end of the string and inserting each substring into the HashSet. Calculating the substring will take O(N) time. Also, the insert operations in the HashSet will take time equal to the length of the string being inserted. Thus, the total time complexity will be O(N^3).

Java (SE 1.8)

/*

    Time Complexity: O(N^3)

    Space Complexity: O(N^2)



    Where 'N' is the length of the given string.

*/



import java.util.HashSet;



public class Solution 

{

    public static int countDistinctSubstrings(String s) 

    {

        //    For storing all distinct substrings of the given string.

        HashSet distinctStrings = new HashSet();



        int n = s.length();



        //    Iterate through the string.

        for (int i = 0; i < n; i++) 

        {

            //    Iterate till the end.

            for (int j = i; j < n; j++) 

            {

                //    Current substring

                String temp = s.substring(i, j+1);



                //    Insert the current substring into the HashSet.

                distinctStrings.add(temp);

            }

        }



        //    Return the total number of distinct substrings.

        return (distinctStrings.size() + 1);

    }

}

Python (3.5)

'''

    Time Complexity: O(N^3)

    Space Complexity: O(N^2)



    Where 'N' is the length of the given string.

'''





def countDistinctSubstrings(s):

    # Set to store all our substrings

    store = set()

    for i in range(len(s)):

        for j in range(i, len(s)):

            # Inserting the current substring

            store.add(s[i:j + 1])



    # Return the length of the set + 1 for empty substring

    return len(store) + 1

Accepted Answer

Trie(HashMap) based Approach

The idea is to build a trie for all suffixes of the given string. We will use the fact that every substring of ‘S’ can be represented as a prefix of some suffix string of ‘S’. Hence, if we create a trie of all suffixes of ‘S’ then the number of distinct substrings will be equal to the nodes in the trie. This is because for every substring there will be only one path from the root node of the trie to the last character of the substring, hence no duplicate substrings will be present in the trie.

The trie class structure is as follows:

class TrieNode
{
public:
    unordered_map children;
};

The steps are as follows :

Iterate through the given string, let’s say our current index is ‘i’.
1. Insert the suffix starting at index ‘i’ of the given string into the trie.
Now to count the number of nodes in the trie we will use recursion. Let’s define a function countNodes(root) where “root” denotes the current node of the trie. This function will return the number of nodes in the subtree of the “root”.
1. Initialize a variable “subtreeNodes” to 1, we will use this variable to count the number of nodes in the subtree of the current node. We are initializing the variable to 1 because the current node will also be counted in the subtree.
2. Iterate through the children nodes of the current node, let’s say we are currently at the ‘i’ th child.
  1. If the current child node is not null then recursively call the function for all children of the current node i.e. countNodes(root->child[i]) and add the value returned by this function call to “subtreeNodes”.
3. Return the value of “subtreeNodes”
Return the number of nodes of the trie as this will be the number of distinct substrings in the given string.

Space Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the given string.

We are inserting each suffix into a trie. So in the worst case when all the characters in the string are distinct, there will be N^2 nodes in the trie. Thus, the overall space complexity will be O(N^2).

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the given string.

We are inserting each suffix of the given string into the trie. There will be N different suffixes and inserting each suffix will take O(N) time. Thus, the total time complexity will be O(N^2).

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where 'N' is the length of the given string.

'''





class TrieNode:

    """A trie node"""



    def __init__(self, char):

        # Character stored in this node

        self.char = char



        # A flag that marks if the word ends on this particular node.

        self.end_of_word = False



        # A dictionary of child nodes where the keys are the characters (letters)

        # and values are the nodes

        self.children = {}





class Trie:

    def __init__(self):

        self.root = TrieNode("")

        self.nodeCnt = 1



    # to insert a suffix into the trie

    def insert(self, s):

        node = self.root



        for char in s:

            # If node for that character does not exist, create it

            if char not in node.children:

                new_node = TrieNode(char)

                node.children[char] = new_node

                node = new_node

                self.nodeCnt += 1

            else:

                node = node.children[char]





def countDistinctSubstrings(s):

    n = len(s)

    trie = Trie()

    for i in range(n):

        trie.insert(s[i:])



    # Return the final node count

    return trie.nodeCnt

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where 'N' is the length of the given string.

*/



import java.util.HashMap;



//    Class for making trie



class TrieNode 

{

    public HashMap children;



    TrieNode() 

    {

        children = new HashMap();

    }

}



public class Solution 

{

    //    Function to insert a string into the trie.

    private static void insert(String s, int i, TrieNode head) 

    {

        TrieNode temp = head;

        int n = s.length();



        //    Iterate through the given string

        while (i < n) 

        {

            char ch = s.charAt(i);

            //    If child node is not present.

            if (temp.children.containsKey(ch) == false) 

            {

                //    Create new child node.

                temp.children.put(ch, new TrieNode());

            }

            //    Move to the child node.

            temp = temp.children.get(ch);

            i++;

        }

    }



    //    Function to count the number of nodes in the trie.

    private static int countNodes(TrieNode root) 

    {



        int subTreeNodes = 1;



        //    Iterate through the children of the current node.

        for (HashMap.Entry i : root.children.entrySet()) 

        {

            subTreeNodes += countNodes(i.getValue());

        }



        return subTreeNodes;

    }



    public static int countDistinctSubstrings(String s) 

    {

        int n = s.length();



        //    Intialize the root of  the trie.

        TrieNode head = new TrieNode();



        //    Insert all suffixes into the trie.

        for (int i = 0; i < n; i++) 

        {

            insert(s, i, head);

        }



        //    Count the total number of nodes in the trie.

        int totalNodes = countNodes(head);



        //    Return the number of distinct substrings.

        return totalNodes;

    }

}

Accepted Answer

Trie(Array) based Approach

The approach is very similar to the previous approach, however, in this approach, we will use an array to store the children of a node to improve the access time of a node. Ofcourse we will be worst in space but we can avoid the collision in and Hashing which takes more time than the random access of array’s elements.

Each node will have a maximum of 26 children nodes as there are a maximum of 26 distinct characters possibles. Hence we can use an array to store the children nodes.

The idea is to build a trie for all suffixes of the given string. We will use the fact that every substring of ‘S’ can be represented as a prefix of some suffix string of ‘S’. Hence, if we create a trie of all suffixes of ‘S’ then the number of distinct substrings will be equal to the nodes in the trie. This is because for every substring there will be only one path from the root node of the trie to the last character of the substring, hence no duplicate substrings will be present in the trie.

The trie class structure is as follows:

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

The steps are as follows :

Iterate through the given string, let’s say our current index is ‘i’.
1. Insert the suffix starting at index ‘i’ of the given string into the trie.
Now to count the number of nodes in the trie we will use recursion. Let’s define a function countNodes(root) where “root” denotes the current node of the trie. This function will return the number of nodes in the subtree of the “root”.
1. Initialize a variable “subtreeNodes” to 1, we will use this variable to count the number of nodes in the subtree of the current node. We are initializing the variable to 1 because the current node will also be counted in the subtree.
2. Iterate through the children nodes of the current node, let’s say we are currently at the ‘i’ th child.
  1. If the current child node is not null then recursively call the function for all children of the current node i.e. countNodes(root->child[i]) and add the value returned by this function call to “subtreeNodes”.
3. Return the value of “subtreeNodes”
Return the number of nodes of the trie as this will be the number of distinct substrings in the given string.

Space Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the given string.

We are inserting each suffix into a trie. So in the worst case when all the characters in the string are distinct, there will be N^2 nodes in the trie. Thus, the overall space complexity will be O(N^2).

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the length of the given string.

We are inserting each suffix of the given string into the trie. There will be N different suffixes and inserting each suffix will take O(N) time. Thus, the total time complexity will be O(N^2).

Java (SE 1.8)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where 'N' is the length of the given string.

*/



//    Class for making trie

class TrieNode 

{

    public TrieNode []children = new TrieNode[26];

    TrieNode() 

    {

        for (int i = 0; i < 26; i++) 

        {

            children[i] = null;

        }

    }

}



public class Solution 

{

    //    Function to insert a string into the trie.

    private static void insert(String s, int i, TrieNode head) 

    {

        TrieNode temp = head;

        int n = s.length();



        //    Iterate through the given string

        while (i < n) 

        {

            char ch = s.charAt(i);



            //    If child node is not present.

            if (temp.children[ch - 'a'] == null) 

            {

                //    Create new child node.

                temp.children[ch - 'a'] = new TrieNode();

            }



            //    Move to the child node.

            temp = temp.children[ch - 'a'];

            i++;

        }

    }



    //    Function to count the number of nodes in the trie.

    private static int countNodes(TrieNode root) 

    {

        if (root == null) 

        {

            return 0;

        }



        int subTreeNodes = 1;



        //    Iterate through the children of the current node.

        for (int i = 0; i < 26; i++) 

        {

            subTreeNodes += countNodes(root.children[i]);

        }



        return subTreeNodes;

    }



    public static int countDistinctSubstrings(String s) 

    {

        int n = s.length();



        //    Intialize the root of  the trie.

        TrieNode head = new TrieNode();



        //    Insert all suffixes into the trie.

        for (int i = 0; i < n; i++) 

        {

            insert(s, i, head);

        }



        //    Count the total number of nodes in the trie.

        int totalNodes = countNodes(head);



        //    Return the number of distinct substrings.

        return totalNodes;

    }

}

Python (3.5)

'''

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where 'N' is the length of the given string.

'''





class TrieNode:

    """A trie node"""



    def __init__(self, pos):

        # position stored in this node

        self.position = pos



        # A flag that marks if the word ends on this particular node.

        self.end_of_word = False



        # children is the array which serves as index for the characters. There are 26 different characters

        # Therefore the size of the array is 26

        self.children = [0] * 26





class Trie:

    def __init__(self):

        self.root = TrieNode("")

        self.nodeCnt = 1



    # to insert a suffix into the trie

    def insert(self, s):

        node = self.root



        for char in s:

            pos = ord(char) - ord('a')

            # If node for that character does not exist, create it

            if node.children[pos] == 0:

                new_node = TrieNode(pos)

                node.children[pos] = new_node

                node = new_node

                self.nodeCnt += 1

            else:

                node = node.children[pos]





def countDistinctSubstrings(s):

    n = len(s)

    trie = Trie()

    for i in range(n):

        trie.insert(s[i:])



    return trie.nodeCnt

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2)

    Space Complexity: O(N^2)



    Where 'N' is the length of the given string.

*/



//    Class for making trie

class TrieNode

{

public:

    TrieNode *children[26];



    TrieNode()

    {



        for (int i = 0; i < 26; i++)

        {

            children[i] = NULL;

        }

    }



    ~TrieNode()

    {

        for (int i = 0; i < 26; i++)

        {

            if (children[i] != NULL)

            {

                delete children[i];

            }

        }

    }

};



//    Function to insert a string into the trie.

void insert(string &s, int i, TrieNode *head)

{

    TrieNode *temp = head;



    int n = s.length();



    //    Iterate through the given string

    while (i < n)

    {

        char ch = s[i];



        //    If child node is not present.

        if (temp->children[ch - 'a'] == NULL)

        {

            //    Create new child node.

            temp->children[ch - 'a'] = new TrieNode();

        }



        //    Move to the child node.

        temp = temp->children[ch - 'a'];

        i++;

    }

}



//    Function to count the number of nodes in the trie.

int countNodes(TrieNode *root)

{

    if (root == NULL)

    {

        return 0;

    }



    int subTreeNodes = 1;



    //    Iterate through the children of the current node.

    for (int i = 0; i < 26; i++)

    {

        subTreeNodes += countNodes(root->children[i]);

    }



    return subTreeNodes;

}



int countDistinctSubstrings(string &s)

{

    int n = s.length();



    //    Intialize the root of  the trie.

    TrieNode *head = new TrieNode();



    //    Insert all suffixes into the trie.

    for (int i = 0; i < n; i++)

    {



        insert(s, i, head);

    }



    //    Count the total number of nodes in the trie.

    int totalNodes = countNodes(head);



    //    Free the memory.

    delete head;



    //    Return the number of distinct substrings.

    return totalNodes;

}

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.

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Adobe Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern