201. Count Distinct Substrings of a String

Given a string s, count the number of distinct non-empty substrings it contains (substrings with the same characters count only once, even if they occur at different positions).

Input: A single line containing the string s. Output: Print a single integer - the number of distinct non-empty substrings of s.

1 <= |s| <= 2000

This is a genuinely elegant reduction: an intimidating-sounding 'count distinct substrings' problem collapses into 'count distinct trie nodes across all suffixes' - a great example of finding the right lens to view a problem through.

Count how many DIFFERENT (non-repeated) pieces of a string exist, where a 'piece' is any continuous chunk of characters. The same chunk of text appearing twice at different positions only counts once. Brute force: Generate every possible substring directly (every start and end position pair), put them all into a hash set to remove duplicates, and count the set's size - this works but costs O(n²) substrings, each potentially O(n) to store/compare, giving O(n³) or so overall, too slow for longer strings. Optimised: Every distinct substring is exactly a prefix of SOME suffix of the string - so instead of generating every substring directly, insert every suffix into a trie ONE character at a time; because the trie automatically merges shared prefixes into shared nodes, the total number of DISTINCT nodes created (excluding the root) directly equals the number of distinct substrings, with no duplicate-counting bookkeeping needed at all.

Generate every one of the O(n^2) substrings by picking every possible start and end index, and insert each one into a hash set of strings, which automatically discards duplicates via full-content hashing/comparison. After processing all of them, the set's size is the count of distinct substrings, but since comparing or hashing a substring costs time proportional to its own length (up to n), this repeats a lot of character-by-character work across overlapping substrings. Time: O(n^3) Space: O(n^2)

Build a suffix automaton of the string incrementally in linear time - a compact automaton whose states represent equivalence classes of substrings sharing the same set of ending positions. Each state has a length (the longest substring reaching it) and a suffix link to another state (whose length is the longest shorter common suffix-class); the number of distinct substrings attributable to a state is exactly length(state) - length(link(state)), so summing this over every state gives the total distinct substring count directly from the automaton's structure. Time: O(n) Space: O(n)

Build a suffix array of the string (all n suffixes sorted lexicographically) together with its LCP array, which records how many leading characters each pair of adjacent sorted suffixes shares. The total number of substrings overall is n(n+1)/2, but each LCP value counts substrings shared as prefixes between neighboring suffixes and so gets double-counted; subtracting the sum of the entire LCP array from n(n+1)/2 gives exactly the count of distinct substrings. Time: O(n log n) Space: O(n)

1. List out every SUFFIX of the string (the whole string, then everything after removing the first character, then after removing the first two, and so on). 2. Insert every one of these suffixes into a trie, one character at a time. 3. Every node created in the trie (other than the root) corresponds to exactly one distinct substring - because a substring is really just a PREFIX of some suffix. 4. Count the total number of nodes created (excluding the root) - that count is the number of distinct substrings.

Time: Inserting all n suffixes, each up to length n, costs roughly O(n²) character-insertions in the straightforward trie approach - much better than the cubic brute force, though a suffix-automaton-based approach (well beyond this lesson's scope) can push it down to O(n). Space: O(n²) in the worst case, for storing all the distinct trie nodes across all suffixes.

Test a single-character string, a string of all identical characters (e.g. 'aaaa', where many substrings collapse to the same value), and the maximum length |s|=2000 for performance.

Be ready to explain WHY 'every distinct substring is a prefix of some suffix' - this single insight is the entire key to this problem, and interviewers often ask you to justify it, not just apply it.