DSA Tracker

Visualize

Count Distinct Substrings (Trie)

Insert every suffix; 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 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.

Details

Animated on: Given a string, count the total number of distinct non-empty substrings that can be formed from it. Example: s = "aba".

Problem:Count Distinct Substrings (Trie)Medium

Insert every suffix; count the new nodes

step 1 / 11

•

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

Every step in words

Show all 11 steps
  1. s = "aba". Insert every suffix of s into a trie; each NEW node created is one distinct substring never seen before.
  2. Suffix 1/3: "aba" (starting at index 0). Walk it down from the root, one character at a time.
  3. 'a' has no child here yet, so a new node "a" is created — that is substring "a", never counted before. Running total: 1.
  4. 'b' has no child here yet, so a new node "ab" is created — that is substring "ab", never counted before. Running total: 2.
  5. 'a' has no child here yet, so a new node "aba" is created — that is substring "aba", never counted before. Running total: 3.
  6. Suffix 2/3: "ba" (starting at index 1). Walk it down from the root, one character at a time.
  7. 'b' has no child here yet, so a new node "b" is created — that is substring "b", never counted before. Running total: 4.
  8. 'a' has no child here yet, so a new node "ba" is created — that is substring "ba", never counted before. Running total: 5.
  9. Suffix 3/3: "a" (starting at index 2). Walk it down from the root, one character at a time.
  10. '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 5.
  11. Every suffix is inserted. The trie ended up with 5 nodes below the root — one per distinct non-empty substring of "aba" — 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 (Trie) in the editorAll Trie problemsBack to roadmap