Pattern visualizer

Count Distinct Substrings Using Trie

Every substring is a prefix of exactly one suffix of the string. Inserting all n suffixes into a trie maps each distinct substring to exactly one node, because a trie automatically merges shared prefixes onto the same path. So instead of hashing O(n^2) substrings, just insert every suffix and count how many BRAND NEW nodes get created along the way — that count is the answer. Animated on: Given a string, count the total number of distinct non-empty substrings that can be formed from it. Example: s = "aba"..

Insert every suffix; count the new nodes

time O(n^2)space O(n^2)step 1 / 11

•

line 3

s = "aba". Insert every suffix of s into a trie; each NEW node created is one distinct substring never seen before.

Pseudocode

1FUNCTION countDistinctSubstrings(s):
2  count <- 0
3  root <- new TrieNode
4  FOR i <- 0 TO LENGTH(s) - 1:
5    cur <- root
6    FOR j <- i TO LENGTH(s) - 1:
7      c <- s[j]
8      IF c NOT IN cur.children:
9        cur.children[c] <- new TrieNode
10        count <- count + 1
11      cur <- cur.children[c]
12  RETURN count

← / → step · space play · Home restart

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap