145. Number of distinct substrings in a string
Given a string s, determine the number of distinct substrings (including the empty substring) of the given string.
A string B is a substring of a string A if B can be obtained by deleting several characters (possibly none) from the start of A and several characters (possibly none) from the end of A.
Two strings X and Y are considered different if there is at least one index i such that the character of X at index i is different from the character of Y at index i (X[i] != Y[i]).
Example 1:
Input : s = "aba"
Output : 6
Explanation :
The distinct substrings are "a", "ab", "ba", "b", "aba", "".
Example 2:
Input : s = "abc"
Output : 7
Explanation :
The distinct substrings are "a", "ab", "abc", "b", "bc", "c", "".
Now Your Turn!
Pick the correct output for the given inputInput : s = "aaabc"
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= s.length <= 103
- s consist of only lowercase English letters.