Pattern visualizer

Number of Distinct Substrings in String

Every substring is a prefix of exactly one suffix of the string. Inserting all n suffixes into a trie maps each distinct substring onto exactly one node, because a trie merges shared prefixes onto the same path automatically. So instead of storing O(n^2) substrings in a hash set, insert every suffix and count how many BRAND NEW nodes get created along the way — that count is the answer. The empty prefix at the root is never counted. Animated on: Given a string, count the total number of distinct non-empty substrings it contains. Example: s = "aab"..

Insert every suffix into a trie; count the new nodes

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

•

line 2

s = "aab". A trie built from every suffix has exactly one node per distinct substring, so inserting each suffix and counting the BRAND NEW nodes created gives the answer.

Pseudocode

1total <- 0
2root <- new node
3FOR i <- 0 TO LENGTH(s) - 1
4  cur <- root
5  FOR j <- i TO LENGTH(s) - 1
6    ch <- s[j]
7    IF ch NOT IN cur.children
8      cur.children[ch] <- new node
9      total <- total + 1
10    cur <- cur.children[ch]
11RETURN total

← / → step · space play · Home restart

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap