All problems
Suffix Trie Count Distinct Substrings
Problem
Count the distinct substrings of a string using a suffix trie.
Insert every suffix of s into a trie. Each newly created node corresponds to one distinct substring, so counting created nodes counts distinct substrings, excluding the empty substring.
Return the number of distinct substrings.
Hint
A substring is determined by a path from the root, so distinct paths equal distinct substrings.
Test cases
case 1
in: ["aba"]
expected: 5
case 2
in: ["aaa"]
expected: 3
case 3
in: [""]
expected: 0
case 4
in: ["abc"]
expected: 6
case 5
in: ["abab"]
expected: 7
Starter codePython
def count_distinct_substrings(s):
# Your code here
pass5 test cases · run your code against them in the editor