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:

1
2
3


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:

1
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

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

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


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
    }
}

1
2
3
4
5
6
7
8


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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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.

Problem#

Examples#

Solution#

Method 1 – Trie (Suffix Trie) or Rolling Hash#

Intuition#

Approach#

Code#

Complexity#