Count Distinct Substrings with Suffix Array

Problem

Build a suffix array and count distinct substrings without a trie.

Sort the starting indices of all suffixes lexicographically and compute the longest common prefix of each adjacent pair. The number of distinct substrings is n(n+1)/2 minus the sum of those LCP lengths, since repeated substrings are exactly the shared prefixes counted once per adjacent pair.

Return [suffix_array, distinct_substring_count].

Hint

Every adjacent suffix pair contributes its longest common prefix as substrings already counted.

Test cases

case 1

in: ["aba"]

expected: [[2,0,1],5]

case 2

in: ["aaa"]

expected: [[2,1,0],3]

case 3

in: [""]

expected: [[],0]

case 4

in: ["abc"]

expected: [[0,1,2],6]

case 5

in: ["abab"]

expected: [[2,0,3,1],7]

Starter codePython

def suffix_array_distinct(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor