DSA Tracker

Visualize

Count Distinct Substrings

Insert every suffix into a trie; count the new nodes

time O(n^2)space O(n^2)

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.

Details

Animated on: Given a string, count the total number of distinct non-empty substrings it contains. Example: s = "aab".

Problem:Count Distinct SubstringsMedium

Insert every suffix into a trie; count the new nodes

step 1 / 11

•

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

Every step in words

Show all 11 steps
  1. 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.
  2. Suffix 1/3: "aab" (starts at index 0). Walk it down from the root, one character at a time.
  3. 'a' has no child here, so a new node "a" is created — substring "a" has never been seen before. Running total: 1.
  4. 'a' has no child here, so a new node "aa" is created — substring "aa" has never been seen before. Running total: 2.
  5. 'b' has no child here, so a new node "aab" is created — substring "aab" has never been seen before. Running total: 3.
  6. Suffix 2/3: "ab" (starts at index 1). Walk it down from the root, one character at a time.
  7. 'a' already exists as this child (node "a" was built by an earlier suffix), so we just follow the link — no new node, total stays 3.
  8. 'b' has no child here, so a new node "ab" is created — substring "ab" has never been seen before. Running total: 4.
  9. Suffix 3/3: "b" (starts at index 2). Walk it down from the root, one character at a time.
  10. 'b' has no child here, so a new node "b" is created — substring "b" has never been seen before. Running total: 5.
  11. Every suffix of "aab" is inserted. The trie ended up with 5 nodes below the root — one per distinct non-empty substring — so the answer is 5.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Distinct Substrings in the editorAll Trie problemsBack to roadmap