Count Distinct Substrings
MediumStringHash TableMath
Description
Given a string s, return the number of distinct non-empty substrings of s.
Examples
Input:
s = "abc"Output:
6Explanation:
Distinct substrings of 'abc' are a, b, c, ab, bc, abc — six in total.
Input:
s = "aaa"Output:
3Explanation:
All non-empty substrings of 'aaa' are a, aa, aaa — three distinct.
Input:
s = "abab"Output:
7Explanation:
Distinct substrings of 'abab' are a, b, ab, ba, aba, bab, abab — seven in total.
Constraints
- •
1 ≤ s.length ≤ 200 - •
s consists of lowercase English letters.