Number of Distinct Substrings in a String

Given a string s, return the number of distinct non-empty substrings of s.

A substring is a contiguous sequence of characters within the string.

Examples

Example 1:

Input: s = "aabb"

Output: 8

Explanation: The 8 distinct substrings are: "a", "aa", "aab", "aabb", "ab", "abb", "b", "bb".

Example 2:

Input: s = "abcabc"

Output: 15

Explanation: There are 21 total substrings but only 15 are distinct since some repeat (e.g., "a", "ab", "abc", "bc", etc.).

Example 3:

Input: s = "aaa"

Output: 3

Explanation: The 3 distinct substrings are: "a", "aa", "aaa".

Constraints

• 1 <= s.length <= 500
• s consists of lowercase English letters