1. Explain how to count all distinct substrings of a string efficiently.
Difficulty: HardType: SubjectiveTopic: Substring Counting
Naively, generating all substrings takes O(n²) and checking uniqueness takes extra time. Efficient methods use suffix trees or suffix arrays with LCP (Longest Common Prefix) array. The number of distinct substrings equals n*(n+1)/2 minus the sum of LCP values. Time complexity: O(n log n) for suffix array method.
Example code
// Distinct substrings = n*(n+1)/2 - sum(LCP) // Example: s = 'aba' // Suffixes: a, aba, ba // Sorted: a, aba, ba // LCP = [1,0] => sum=1 // Distinct substrings = 3*(4)/2 - 1 = 5 // Substrings: a, ab, aba, b, ba