We need to count how many unique substrings exist in the given string. A substring is any contiguous portion of the string, and we only want to count each unique one once. The empty string does not count.

For example, in "aba", the substrings are: "a", "b", "a", "ab", "ba", "aba". But "a" appears twice, so the distinct count is 5 (not 6).

The total number of substrings in a string of length n is n*(n+1)/2 (picking a start and end position). The challenge is counting how many of those are duplicates. We can enumerate all substrings and add them to a set, or we can use a Trie or rolling hash to avoid creating string objects at all.

Key Constraints:

Intuition

Generate every possible substring, add it to a HashSet, and let the set handle deduplication. At the end, the size of the set is the answer.

For a string of length n, we pick every starting index i (0 to n-1) and every ending index j (i+1 to n), extract the substring s[i..j], and add it to the set. Duplicates collapse to a single entry.

The cost is in the substring extraction. Each call creates a new string object, and hashing that string takes time proportional to its length. So while the two loops are O(n^2), the work per substring can be up to O(n), making this O(n^3) overall.

Algorithm

Visualization and Code

The next approach avoids rebuilding and rehashing strings by reusing the work already done for shorter substrings.

Intuition

Every substring of s is a prefix of some suffix of s. In "abc", the substring "ab" is a prefix of the suffix "abc", and "bc" is a prefix of the suffix "bc". So if we insert all n suffixes of s into a Trie, the set of all root-to-node paths covers exactly the set of substrings of s.

That turns the count into a node-counting problem: insert every suffix into a Trie, and each time inserting a character creates a new node, that node is one distinct substring not seen before. The total number of nodes created equals the number of distinct substrings.

This avoids creating string objects. We walk character by character, either following an existing edge or creating a new node.

Algorithm

Visualization and Code

The Trie uses O(n^2 * 26) space because each node stores an array of 26 children. The next approach represents each substring as a single number instead of a node, which lowers the per-entry memory.

Intuition

Represent each substring by a hash instead of by a node, and store the hashes in a set. The number of distinct hashes equals the number of distinct substrings, as long as no two different substrings collide to the same hash.

A polynomial rolling hash makes extending a substring cheap. Fixing the start index i and growing the end index j by one, the hash of s[i..j+1] is hash * base + s[j+1], computed from the previous hash in O(1). So for each start position we sweep the end position once, hashing all n*(n+1)/2 substrings in O(n^2) total time.

The risk is a hash collision: two distinct substrings mapping to the same value would be counted once and undercount the answer. To make that improbable, we hash each substring under two independent base-modulus pairs and treat a substring as seen only when both hashes match.

Algorithm

Visualization and Code