PPractick

The problem

You're building a search-suggestion/autocomplete indexing engine. To estimate how rich the indexable content is for a given document, your team wants a metric: the total number of distinct substrings in a string. This becomes the basis for a more advanced "substring diversity score" feature. Given a string s, return the count of all distinct (non-empty) substrings.

Example: s = "ababa" → there are 9 distinct substrings: "a", "b", "ab", "ba", "aba", "bab", "abab", "baba", "ababa".

Function signature

int countDistinctSubstrings(string s);

Test cases

Input s	Output	Explanation
"ababa"	9	Listed above — note total possible substrings would be 5*6/2=15, but duplicates reduce it to 9
"aaaa"	4	Only "a", "aa", "aaa", "aaaa" — all repeats of the same character collapse to 4 distinct entries
"abc"	6	All substrings unique: "a","b","c","ab","bc","abc"
"a"	1	Just "a"
""	0	Empty string has no substrings
"aaa"	3	"a","aa","aaa"
"abab"	7	"a","b","ab","ba","aba","bab","abab" (note: "ab" appears twice as a substring occurrence, counted once)

How interviewers phrase it

• "Given a string, how many distinct substrings does it contain?"
• "Build a data structure that lets you count all unique substrings of a string efficiently."
• This is a classic Trie application problem, but can also be solved with suffix arrays + LCP or suffix automaton — interviewers may probe which approach you pick and why, since this is a good signal of algorithmic breadth.

Clarifying questions to ask

1. Does "substring" include the empty substring? (Standard convention: no, only non-empty substrings count — confirm.)
2. What's the expected length of s? (Critical — naive approaches are O(n³) or O(n² log n); for large n (like 10⁴–10⁵), you need O(n²) Trie or O(n log n) suffix array/automaton approaches.)
3. Should I just return the count, or do you also want the actual list of distinct substrings? (Returning the list is inherently more expensive — O(n²) just to enumerate them all, regardless of approach.)
4. Is the alphabet small (e.g., lowercase English letters) or could it be large/Unicode? (Affects Trie branching factor and memory.)

Follow-ups to expect

1. "Walk through the brute-force approach using a hash set — what's its complexity?"
2. "How does the Trie approach improve on this?"
3. "Can you do this in O(n log n) or O(n) — what data structures would you use instead?"
4. "Why does each new Trie node correspond to exactly one distinct substring?"
5. "What's the space complexity tradeoff between the Trie approach and the suffix-array/automaton approaches?"
6. "Can you generalize this to count distinct substrings across MULTIPLE strings (like a generalized suffix trie)?"

Related questions

• Remove Outermost Parentheses Medium
• Reverse words in a given string / Palindrome Check Medium
• Maximum Nesting Depth of the Parentheses Medium
• Roman to Integer Medium
• String to Integer (atoi) Medium
• Longest Palindromic Substring Medium

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in