Number of distinct substrings in a string

Intuition

We can find all distinct substrings of a string by starting at each character and extending to the end, creating every possible substring. Storing these substrings in a set filters out duplicates, ensuring unique substrings are counted.

Approach

Initialize an empty set to store distinct substrings.
Use an outer loop to iterate through each character of the string. This character will serve as the starting point for substrings.
Construct Substrings:
- For each starting character, use a nested loop to construct all possible substrings beginning from that character.
- The outer loop sets the starting point, while the inner loop iterates over subsequent characters to form the substring.
- Add each constructed substring to the set. Since sets only store unique values, duplicates will be automatically filtered out.
After iterating through the string and constructing substrings from each starting character, return the size of the set. This will give the number of distinct substrings of the given string.

Dry Run

For detailed dry run watch the video.

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // To Calculate Distinct Substrings
    int countDistinctSubstring(string s) {
        set<string> substrings;
        
        // Iterate through each character of string
        for (int i = 0; i < s.length(); ++i) {
            string substring = "";
           /* Construct all possible substrings 
           starting from the current character*/
            for (int j = i; j < s.length(); ++j) {
                substring += s[j];
                substrings.insert(substring);
            }
        }
        
        // Include empty substring
        substrings.insert("");
        
        // Return number of distinct substrings
        return substrings.size();
    }
};

int main() {
    Solution solution;
    string input = "abc";
    cout << "Number of distinct substrings: " << solution.countDistinctSubstring(input) << endl;
    return 0;
}
import java.util.*;

public class Solution {
    // To Calculate Distinct Substrings
    public int countDistinctSubstring(String s) {
        Set<String> substrings = new HashSet<>();
        
        // Iterate through each character of string
        for (int i = 0; i < s.length(); ++i) {
            String substring = "";
            /* Construct all possible substrings 
            starting from the current character */
            for (int j = i; j < s.length(); ++j) {
                substring += s.charAt(j);
                substrings.add(substring);
            }
        }
        
        // Include empty substring
        substrings.add("");
        
        // Return number of distinct substrings
        return substrings.size();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String input = "abc";
        System.out.println("Number of distinct substrings: " + solution.countDistinctSubstring(input));
    }
}
class Solution:
    def countDistinctSubstring(self, s: str) -> int:
        substrings = set()
        
        # Iterate through each character of the string
        for i in range(len(s)):
            substring = ""
            ''' Construct all possible substrings 
            starting from the current character '''
            for j in range(i, len(s)):
                substring += s[j]
                substrings.add(substring)
        
        # Include empty substring
        substrings.add("")
        
        # Return number of distinct substrings
        return len(substrings)

# Test the solution
solution = Solution()
input_str = "abc"
print("Number of distinct substrings:", solution.countDistinctSubstring(input_str))
class Solution {
    // To Calculate Distinct Substrings
    countDistinctSubstring(s) {
        let substrings = new Set();
        
        // Iterate through each character of the string
        for (let i = 0; i < s.length; ++i) {
            let substring = "";
            /* Construct all possible substrings 
            starting from the current character */
            for (let j = i; j < s.length; ++j) {
                substring += s[j];
                substrings.add(substring);
            }
        }
        
        // Include empty substring
        substrings.add("");
        
        // Return number of distinct substrings
        return substrings.size;
    }
}

// Test the solution
const solution = new Solution();
const input = "abc";
console.log("Number of distinct substrings:", solution.countDistinctSubstring(input));

Complexity Analysis

Time Complexity: O(N² X log M) where N is the size of the string and M is the number of elements in the set. Constructing all possible substrings involves O(N²) operations. Each substring insertion into the set takes O(log M) time due to the balanced tree structure of the set, ensuring uniqueness. Space Complexity: O(N³), where N is the length of the string. This complexity arises because there can be up to O(N²) distinct substrings, and each substring can be up to N characters long. Storing all these substrings requires O(N²) substrings times O(N) length, resulting in O(N³) space.

Intuition

Instead of using nested loops in the previous approach, use a Trie data structure which will minimize the number of comparisons required while traversing the substrings. The idea is to store only essential information and reduce redundancy by sharing common prefixes among substrings. This approach is particularly advantageous for long strings with many repeated substrings, as it optimizes space utilization.

Approach

Start by initializing a root node for the Trie.
Iterate through the input string. For each character:
- Traverse the Trie, creating new nodes as necessary to represent the substrings formed by the characters seen so far.
Initialize a counter to keep track of the number of distinct substrings.
- Iterate through all possible starting positions of the substring.
- Begin from the root node for each substring.
- For each character in the substring starting from the current position:
  - Check if the current node has a child node for that character.
  - If not, insert a new child node and increment the counter, indicating a new substring is found.
  - Move to the child node corresponding to the current character.
- Repeat this process for all substrings starting from the current position.
Finally, return the total count of distinct substrings, adding one to account for the empty string.

Dry Run

For detailed dry run watch the video.

Solution

#include <bits/stdc++.h>
using namespace std;

// Node structure
struct Node {

    Node* links[26];

    bool containsKey(char ch) {
        return links[ch - 'a'] != nullptr;
    }

    void put(char ch, Node* node) {
        links[ch - 'a'] = node;
    }

 
    Node* get(char ch) {
        return links[ch - 'a'];
    }
};

class Solution {
public:
    // Count number of distinct substrings in string
    int countDistinctSubstring(string s) {
        int c = 0; 
         // Root node of the trie
        Node* root = new Node();

        // Iterate all starting positions of substrings
        for (int i = 0; i < s.size(); i++) {
            Node* node = root;

            // Iterate through characters 
            for (int j = i; j < s.size(); j++) {
                /*If the current character is not 
                a child of the current node, 
                insert it as a new child node*/
                if (!node->containsKey(s[j])) {
                    c++; 
                    // Insert new child node for character s[j]
                    node->put(s[j], new Node()); 
                }
                // Move to the child node 
                node = node->get(s[j]); 
            }
        }

        // Clean up the allocated memory
        deleteTrie(root);
        /*Return the total 
        count of distinct 
        substrings including 
        the empty string*/
        return c+1; 
    }

private:
    // Freeing up memory
    void deleteTrie(Node* node) {
        for (int i = 0; i < 26; i++) {
            if (node->links[i] != nullptr) {
                deleteTrie(node->links[i]);
            }
        }
        delete node;
    }
};

// Main function 
int main() {
    Solution solution;

    // Test case 1
    string s1 = "aabbaba";
    cout << "Input: " << s1 << endl;
    cout << "Number of distinct substrings: " << solution.countDistinctSubstring(s1) << endl;

    // Test case 2
    string s2 = "abcdefg";
    cout << "Input: " << s2 << endl;
    cout << "Number of distinct substrings: " << solution.countDistinctSubstring(s2) << endl;

    return 0;
}
import java.util.*;
class Node {
    Node[] links = new Node[26];  // For 26 lowercase English letters

    boolean containsKey(char ch) {
        return links[ch - 'a'] != null;
    }

    void put(char ch, Node node) {
        links[ch - 'a'] = node;
    }

    Node get(char ch) {
        return links[ch - 'a'];
    }
}

class Solution {
    // Count number of distinct substrings in string
    public int countDistinctSubstring(String s) {
        int count = 0;
        // Root node of the Trie
        Node root = new Node();

        // Iterate over all starting positions of substrings
        for (int i = 0; i < s.length(); i++) {
            Node node = root;

            // Iterate through characters of the substring starting at index i
            for (int j = i; j < s.length(); j++) {
                char currentChar = s.charAt(j);
                // If the current character is not a child of the current node, insert it
                if (!node.containsKey(currentChar)) {
                    count++;
                    // Insert new child node for character s[j]
                    node.put(currentChar, new Node());
                }
                // Move to the child node
                node = node.get(currentChar);
            }
        }

        // Return the total count of distinct substrings including the empty string
        return count + 1;  // +1 to count the empty substring
    }
}
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test case 1
        String s1 = "aba";
        System.out.println("Input: " + s1);
        System.out.println("Number of distinct substrings: " + solution.countDistinctSubstring(s1));

        // Test case 2
        String s2 = "abc";
        System.out.println("Input: " + s2);
        System.out.println("Number of distinct substrings: " + solution.countDistinctSubstring(s2));
    }
}
class Node:
    def __init__(self):
        self.links = [None] * 26

    def containsKey(self, ch):
        return self.links[ord(ch) - ord('a')] is not None

    def put(self, ch, node):
        self.links[ord(ch) - ord('a')] = node

    def get(self, ch):
        return self.links[ord(ch) - ord('a')]


class Solution:
    # Count number of distinct substrings in string
    def countDistinctSubstring(self, s):
        c = 0
        # Root node of the trie
        root = Node()

        # Iterate all starting positions of substrings
        for i in range(len(s)):
            node = root

            # Iterate through characters
            for j in range(i, len(s)):
                '''If the current character is not 
                a child of the current node, 
                insert it as a new child node'''
                if not node.containsKey(s[j]):
                    c += 1
                    # Insert new child node for character s[j]
                    node.put(s[j], Node())
                # Move to the child node
                node = node.get(s[j])

        # Clean up the allocated memory
        self.deleteTrie(root)
        '''Return the total 
        count of distinct 
        substrings including 
        the empty string'''
        return c + 1

    # Freeing up memory
    def deleteTrie(self, node):
        for i in range(26):
            if node.links[i] is not None:
                self.deleteTrie(node.links[i])


# Main function
if __name__ == "__main__":
    solution = Solution()

    # Test case 1
    s1 = "aabbaba"
    print("Input:", s1)
    print("Number of distinct substrings:", solution.countDistinctSubstring(s1))

    # Test case 2
    s2 = "abcdefg"
    print("Input:", s2)
    print("Number of distinct substrings:", solution.countDistinctSubstring(s2))
class Node {
    constructor() {
        this.links = new Array(26).fill(null);
    }

    containsKey(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] !== null;
    }

    put(ch, node) {
        this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)] = node;
    }

    get(ch) {
        return this.links[ch.charCodeAt(0) - 'a'.charCodeAt(0)];
    }
}

class Solution {
    // Count number of distinct substrings in string
    countDistinctSubstring(s) {
        let c = 0;
        // Root node of the trie
        let root = new Node();

        // Iterate all starting positions of substrings
        for (let i = 0; i < s.length; i++) {
            let node = root;

            // Iterate through characters
            for (let j = i; j < s.length; j++) {
                /*If the current character is not 
                a child of the current node, 
                insert it as a new child node*/
                if (!node.containsKey(s[j])) {
                    c++;
                    // Insert new child node for character s[j]
                    node.put(s[j], new Node());
                }
                // Move to the child node
                node = node.get(s[j]);
            }
        }

        // Clean up the allocated memory
        this.deleteTrie(root);
        /*Return the total 
        count of distinct 
        substrings including 
        the empty string*/
        return c + 1;
    }

    // Freeing up memory
    deleteTrie(node) {
        for (let i = 0; i < 26; i++) {
            if (node.links[i] !== null) {
                this.deleteTrie(node.links[i]);
            }
        }
    }
}

// Main function
const solution = new Solution();

// Test case 1
const s1 = "aabbaba";
console.log("Input:", s1);
console.log("Number of distinct substrings:", solution.countDistinctSubstring(s1));

// Test case 2
const s2 = "abcdefg";
console.log("Input:", s2);
console.log("Number of distinct substrings:", solution.countDistinctSubstring(s2));

Complexity Analysis

Time Complexity: O(N^2) where N is the size of the string.This complexity arises because, for each starting position in the string, we iterate through the remaining characters to form substrings. The nested loops result in a quadratic number of operations.

Space Complexity: O(N^2) where N is the size of the string. The space complexity is due to storing all distinct substrings in the trie. In the worst case, the number of distinct substrings can be quadratic relative to the size of the string, leading to O(N^2) space usage.

Problem List

Number of distinct substrings in a string

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code