Count Distinct Substrings via Trie

Description

Given a string s consisting of lowercase English letters, return the total number of distinct substrings of s, including the empty substring.

A substring is a contiguous sequence of characters within a string. For example, "ab" is a substring of "abc", but "ac" is not.

Two substrings are considered different if they differ in at least one character position. Note that the same sequence of characters appearing at different positions in the original string still counts as a single distinct substring.

You should implement the solution using a Trie data structure.

Examples

Example 1

Input: s = "sds"

Output: 6

Explanation: The 6 distinct substrings are: "" (empty), "s", "d", "sd", "ds", "sds". Note that "s" appears at both index 0 and index 2, but it is counted only once since the character content is identical.

Example 2

Input: s = "abc"

Output: 7

Explanation: The 7 distinct substrings are: "", "a", "b", "c", "ab", "bc", "abc". Since all characters are unique, every possible substring is distinct. For a string of length n with all distinct characters, the count is n×(n+1)/2 + 1.

Example 3

Input: s = "abab"

Output: 8

Explanation: The 8 distinct substrings are: "", "a", "b", "ab", "ba", "aba", "bab", "abab". Despite the string having length 4 (which would give 4×5/2 + 1 = 11 total substrings if all were unique), repeated patterns reduce the count to 8. For example, "ab" appears at positions [0,1] and [2,3] but counts only once.

Constraints

1 ≤ s.length ≤ 1000
s consists of only lowercase English letters ('a' to 'z')

Editorial

Brute Force

Intuition

The most straightforward way to count distinct substrings is to simply generate every possible substring and collect them into a set that automatically removes duplicates.

Think of it like going through every possible starting position in the string, and from each starting position, extending the substring one character at a time toward the end. Each time you form a new substring, you drop it into a bucket that only keeps unique entries. At the end, you count how many entries the bucket holds.

For a string of length n, there are n possible starting positions. From each starting position i, you can form substrings of length 1, 2, 3, ..., up to n-i. In total, this gives us n×(n+1)/2 substrings (before deduplication), plus the empty substring.

Step-by-Step Explanation

Let's trace through with s = "sds":

Step 1: Initialize an empty set. Add the empty string "" to it.

Set = {""}
Size = 1

Step 2: Start from index i=0. Extend to j=0: substring = "s".

"s" is NOT in set → add it
Set = {"", "s"}
Size = 2

Step 3: Continue from i=0, extend to j=1: substring = "sd".

"sd" is NOT in set → add it
Set = {"", "s", "sd"}
Size = 3

Step 4: Continue from i=0, extend to j=2: substring = "sds".

"sds" is NOT in set → add it
Set = {"", "s", "sd", "sds"}
Size = 4

Step 5: Move to i=1. Extend to j=1: substring = "d".

"d" is NOT in set → add it
Set = {"", "s", "sd", "sds", "d"}
Size = 5

Step 6: Continue from i=1, extend to j=2: substring = "ds".

"ds" is NOT in set → add it
Set = {"", "s", "sd", "sds", "d", "ds"}
Size = 6

Step 7: Move to i=2. Extend to j=2: substring = "s".

"s" IS already in set → skip (duplicate!)
Set unchanged = {"", "s", "sd", "sds", "d", "ds"}
Size = 6

Step 8: All positions exhausted. Return size = 6.

Notice at Step 7: the character 's' at index 2 forms the same substring "s" that we already found at index 0. The set handles this deduplication automatically. We generated 6 substrings from the nested loops, but the set ended up with 6 distinct entries (including the empty string), confirming 1 duplicate was caught.

Algorithm

Create an empty set of strings and add the empty string "" to it
For each starting index i from 0 to n-1:
- Initialize an empty substring sub
- For each ending index j from i to n-1:
  - Append character s[j] to sub
  - Insert sub into the set (set handles deduplication)
Return the size of the set

Code

#include <unordered_set>
#include <string>
using namespace std;

class Solution {
public:
    int countDistinctSubstrings(string &s) {
        int n = s.length();
        unordered_set<string> distinct;
        distinct.insert(""); // empty substring

        for (int i = 0; i < n; i++) {
            string sub = "";
            for (int j = i; j < n; j++) {
                sub += s[j];
                distinct.insert(sub);
            }
        }

        return distinct.size();
    }
};

class Solution:
    def countDistinctSubstrings(self, s: str) -> int:
        n = len(s)
        distinct = set()
        distinct.add("")  # empty substring

        for i in range(n):
            for j in range(i + 1, n + 1):
                distinct.add(s[i:j])

        return len(distinct)

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countDistinctSubstrings(String s) {
        int n = s.length();
        Set<String> distinct = new HashSet<>();
        distinct.add(""); // empty substring

        for (int i = 0; i < n; i++) {
            StringBuilder sub = new StringBuilder();
            for (int j = i; j < n; j++) {
                sub.append(s.charAt(j));
                distinct.add(sub.toString());
            }
        }

        return distinct.size();
    }
}

Complexity Analysis

Time Complexity: O(n³)

The two nested loops generate O(n²) substrings. For each substring, we need to hash it for set insertion, which takes O(length) time. Since the average substring length is O(n), the total hashing work is O(n² × n) = O(n³). In the worst case (all distinct characters), we generate n×(n+1)/2 substrings, and the hashing cost pushes the total to cubic time.

Space Complexity: O(n² × n) = O(n³)

The set can hold up to n×(n+1)/2 + 1 = O(n²) distinct substrings. Each substring has an average length of O(n/2). Total memory for storing all substring characters is therefore O(n² × n) = O(n³). For n = 1000, this means storing up to ~500 million characters — a severe memory burden.

Why This Approach Is Not Efficient

The brute force approach suffers from two critical bottlenecks:

1. Redundant String Hashing: Every time we create a substring s[i..j], we hash the entire string from scratch. When we extend to s[i..j+1], we hash all j-i+2 characters again instead of building on the previous hash. This repeated work drives the time to O(n³).

2. Massive Memory Consumption: We store every distinct substring as a separate string object in the set. For n = 1000, there can be up to ~500,000 substrings, consuming hundreds of megabytes of memory. Many of these substrings share common prefixes (e.g., "ab", "abc", "abcd" all start with "ab"), yet the set stores each one independently — wasting space on repeated prefix characters.

The Key Insight: If we could share common prefixes across substrings, we would avoid both redundant hashing and redundant storage. A Trie (prefix tree) provides exactly this structure: substrings that share a prefix share the same path in the trie. Inserting a new character only requires creating a single new node (or following an existing one), making each character insertion O(1). Additionally, every node in the trie corresponds to exactly one unique substring, so counting nodes directly gives the answer — no hashing needed.

This reduces both time and space from O(n³) to O(n²).

Optimal Approach - Suffix Trie

Intuition

The core insight behind this approach rests on a beautiful property of strings:

Every substring of a string is a prefix of some suffix of that string.

Let us unpack this. Consider the string "sds". Its suffixes are:

Suffix starting at index 0: "sds"
Suffix starting at index 1: "ds"
Suffix starting at index 2: "s"

Now consider any substring, say "sd". This is the prefix of length 2 of the suffix "sds". Similarly, "d" is the prefix of length 1 of the suffix "ds".

So if we could efficiently collect all prefixes of all suffixes, we would have all substrings. A Trie (prefix tree) does exactly this. When we insert a string into a trie, every node on the insertion path represents a prefix of that string. So inserting all suffixes into a trie means every node represents a prefix of some suffix — which is a substring.

The counting trick: Each node in the trie corresponds to exactly one unique substring. Shared prefixes share the same node (deduplication is automatic). So the total number of distinct substrings equals the total number of nodes in the trie (counting the root as the empty substring).

Instead of inserting whole suffixes and then counting nodes, we can count during insertion: every time we create a new trie node, we have discovered a new distinct substring. Nodes that already exist represent substrings we have already counted.

Suffix trie for 'sds' showing all suffixes inserted and each node mapped to a distinct substring

Step-by-Step Explanation

Let's trace the suffix trie construction for s = "sds":

The suffixes to insert are: "sds" (index 0), "ds" (index 1), "s" (index 2).

Step 1: Initialize an empty trie with only a root node. The root represents the empty substring. Node count = 1.

Step 2: Insert suffix "sds". Process character 's': root has no child 's' → create new node. This node represents substring "s". Count = 2.

Step 3: Continue suffix "sds". Process character 'd': the 's' node has no child 'd' → create new node. This represents substring "sd". Count = 3.

Step 4: Continue suffix "sds". Process character 's': the 'd' node has no child 's' → create new node. This represents substring "sds". Suffix fully inserted. Count = 4.

Step 5: Insert suffix "ds". Process character 'd': root has no child 'd' → create new node under root. This represents substring "d". Count = 5.

Step 6: Continue suffix "ds". Process character 's': the new 'd' node (under root) has no child 's' → create new node. This represents substring "ds". Suffix fully inserted. Count = 6.

Step 7: Insert suffix "s". Process character 's': root already has a child 's' (created in Step 2). No new node needed — the substring "s" was already discovered. Count stays at 6.

Step 8: All suffixes inserted. Total distinct substrings = node count = 6. The trie has 5 non-root nodes (representing "s", "sd", "sds", "d", "ds") plus the root (representing "").

Building the Suffix Trie for "sds" — Watch how inserting each suffix into the trie creates new nodes for undiscovered substrings, while shared prefixes reuse existing nodes.

Algorithm

Create a trie with a single root node (representing the empty substring)
Initialize a counter count = 0 (to track new non-empty substrings)
For each starting index i from 0 to n-1 (each suffix start):
- Set current pointer to root
- For each index j from i to n-1:
  - Compute the character index: idx = s[j] - 'a'
  - If current has no child at index idx:
    - Create a new trie node at that position
    - Increment count (found a new distinct substring)
  - Move current to the child at index idx
Return count + 1 (add 1 for the empty substring)

Code

struct TrieNode {
    TrieNode* children[26];
    TrieNode() {
        for (int i = 0; i < 26; i++)
            children[i] = nullptr;
    }
};

class Solution {
public:
    int countDistinctSubstrings(string &s) {
        int n = s.length();
        TrieNode* root = new TrieNode();
        int count = 0;

        for (int i = 0; i < n; i++) {
            TrieNode* curr = root;
            for (int j = i; j < n; j++) {
                int idx = s[j] - 'a';
                if (curr->children[idx] == nullptr) {
                    curr->children[idx] = new TrieNode();
                    count++;
                }
                curr = curr->children[idx];
            }
        }

        return count + 1; // +1 for empty substring
    }
};

class TrieNode:
    def __init__(self):
        self.children = {}

class Solution:
    def countDistinctSubstrings(self, s: str) -> int:
        root = TrieNode()
        count = 0

        for i in range(len(s)):
            curr = root
            for j in range(i, len(s)):
                ch = s[j]
                if ch not in curr.children:
                    curr.children[ch] = TrieNode()
                    count += 1
                curr = curr.children[ch]

        return count + 1  # +1 for empty substring

class Solution {
    static final int ALPHABET_SIZE = 26;

    static class TrieNode {
        TrieNode[] children = new TrieNode[ALPHABET_SIZE];
    }

    public int countDistinctSubstrings(String s) {
        int n = s.length();
        TrieNode root = new TrieNode();
        int count = 0;

        for (int i = 0; i < n; i++) {
            TrieNode curr = root;
            for (int j = i; j < n; j++) {
                int idx = s.charAt(j) - 'a';
                if (curr.children[idx] == null) {
                    curr.children[idx] = new TrieNode();
                    count++;
                }
                curr = curr.children[idx];
            }
        }

        return count + 1; // +1 for empty substring
    }
}

Complexity Analysis

Time Complexity: O(n²)

We insert n suffixes into the trie. The suffix starting at index i has length n - i. The total number of character insertions is:

n + (n-1) + (n-2) + ... + 1 = n × (n+1) / 2 = O(n²)

Each character insertion involves a constant-time check (does the child exist?) and potentially creating a new node — both O(1) operations. No string hashing is needed, unlike the brute force approach.

Compared to the brute force O(n³), this is a significant improvement. For n = 1000, the trie approach performs ~500,000 operations versus ~500,000,000 for brute force — a 1000× speedup.

Space Complexity: O(n²)

In the worst case (all distinct characters, e.g., "abcde..."), every suffix insertion creates all-new nodes. The total number of nodes equals n × (n+1) / 2 = O(n²). Each node stores an array of 26 pointers, but since 26 is a constant, the space per node is O(1). Total space is O(n²).

In practice, strings with repeated characters create far fewer nodes because shared prefixes reuse existing nodes. For example, "aaaa" (length 4) only creates 4 nodes instead of 10, because suffixes "aaa", "aa", "a" share the same path in the trie.