MediumTrieAI interview only
Number of Distinct Substrings in a String
Asked atgoogleamazonmicrosoftadobe
01 · Problem
Given a string s, return how many distinct non-empty substrings it contains. A substring is a contiguous block of characters; two substrings count once if they spell the same text, no matter where they occur.
02 · Examples
Example 01
Input
s = "abab"
Output
7
The 10 substrings collapse to 7 distinct ones: "a", "b", "ab", "ba", "aba", "bab" and "abab".
Example 02
Input
s = "abcab"
Output
12
There are 15 substrings in total; "a", "b" and "ab" each appear twice, so 15 - 3 = 12 are distinct.
Example 03
Input
s = "aaa"
Output
3
The distinct substrings are "a", "aa" and "aaa".
03 · Constraints
- 011 <= s.length <= 500
- 02s consists of lowercase English letters only
- 03The empty substring is not counted
- 04The answer fits in a 32-bit signed integer (at most s.length * (s.length + 1) / 2)
04 · Optimal complexity
- Time
- O(n^2)
- Space
- O(n^2)
05 · Two ways to work on it
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.