Number of Distinct Substrings in a String

Problem

Given a string s, return the number ofdistinct substrings of s.

A substring of a string is obtained by deleting any number of characters (possibly zero) from the front of the string and any number (possibly zero) from the back of the string.

Examples

Example 1:

Input: s = "aabbaba"
Output: 21
Explanation: The set of distinct strings is ["a","b","aa","bb","ab","ba","aab","abb","bab","bba","aba","aabb","abba","bbab","baba","aabba","abbab","bbaba","aabbab","abbaba","aabbaba"]

Example 2:

Input: s = "abcdefg"
Output: 28

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Follow up: Can you solve this problem in O(n) time complexity?

Solution

Method 1 – Trie (Suffix Trie) or Rolling Hash

Intuition

Every substring can be represented by its start and end indices. To count distinct substrings, insert all substrings into a trie or use a set of hashes. Trie is efficient for small n, rolling hash for larger n.

Approach

1. For each start index, insert all substrings starting at that index into a trie, counting new nodes.
2. Alternatively, use a set to store hashes of all substrings.
3. Return the total number of distinct substrings.

Code

C++ (Trie)

#include <string>
#include <vector>
using namespace std;
struct Trie {
    vector<Trie*> next;
    Trie() : next(26, nullptr) {}
};
class Solution {
public:
    int countDistinct(string s) {
        Trie* root = new Trie();
        int ans = 0, n = s.size();
        for (int i = 0; i < n; ++i) {
            Trie* node = root;
            for (int j = i; j < n; ++j) {
                int c = s[j]-'a';
                if (!node->next[c]) {
                    node->next[c] = new Trie();
                    ++ans;
                }
                node = node->next[c];
            }
        }
        return ans;
    }
};

Go (Set of Hashes)

func countDistinct(s string) int {
    n := len(s)
    set := map[string]struct{}{}
    for i := 0; i < n; i++ {
        for j := i+1; j <= n; j++ {
            set[s[i:j]] = struct{}{}
        }
    }
    return len(set)
}

Java (Trie)

import java.util.*;
class Trie {
    Trie[] next = new Trie[26];
}
class Solution {
    public int countDistinct(String s) {
        Trie root = new Trie();
        int ans = 0, n = s.length();
        for (int i = 0; i < n; ++i) {
            Trie node = root;
            for (int j = i; j < n; ++j) {
                int c = s.charAt(j)-'a';
                if (node.next[c] == null) {
                    node.next[c] = new Trie();
                    ans++;
                }
                node = node.next[c];
            }
        }
        return ans;
    }
}

Kotlin (Trie)

class Trie { val next = Array<Trie?>(26) { null } }
class Solution {
    fun countDistinct(s: String): Int {
        val root = Trie()
        var ans = 0
        for (i in s.indices) {
            var node = root
            for (j in i until s.length) {
                val c = s[j]-'a'
                if (node.next[c] == null) {
                    node.next[c] = Trie(); ans++
                }
                node = node.next[c]!!
            }
        }
        return ans
    }
}

Python (Set of Substrings)

class Solution:
    def countDistinct(self, s: str) -> int:
        n = len(s)
        seen = set()
        for i in range(n):
            for j in range(i+1, n+1):
                seen.add(s[i:j])
        return len(seen)

Rust (Trie)

struct Trie { next: [Option<Box<Trie>>; 26] }
impl Trie { fn new() -> Self { Trie { next: Default::default() } } }
impl Solution {
    pub fn count_distinct(s: String) -> i32 {
        let n = s.len();
        let s = s.as_bytes();
        let mut root = Trie::new();
        let mut ans = 0;
        for i in 0..n {
            let mut node = &mut root;
            for j in i..n {
                let c = (s[j]-b'a') as usize;
                if node.next[c].is_none() {
                    node.next[c] = Some(Box::new(Trie::new()));
                    ans += 1;
                }
                node = node.next[c].as_mut().unwrap();
            }
        }
        ans
    }
}

TypeScript (Set of Substrings)

class Solution {
    countDistinct(s: string): number {
        const n = s.length;
        const set = new Set<string>();
        for (let i = 0; i < n; ++i)
            for (let j = i+1; j <= n; ++j)
                set.add(s.slice(i, j));
        return set.size;
    }
}

Complexity

• ⏰ Time complexity: O(n^2) for trie/set, O(n) for suffix automaton (not shown).
• 🧺 Space complexity: O(n^2) for trie/set.