Is Number of Distinct Substrings in a String easy or hard?

This problem is generally classified as Medium. The brute force idea is straightforward, but optimizing it using rolling hash or suffix structures requires understanding substring hashing and avoiding repeated substring comparisons.

Number of Distinct Substrings in a String Python/Java solution

In Python or Java, iterate over every starting index and extend the substring while updating a rolling hash value. Insert each hash into a HashSet (Java) or set (Python). The final answer is the size of the set, giving an O(n^2) time and O(n^2) space solution.

How to solve Number of Distinct Substrings in a String in O(n)?

An O(n) or near-linear solution can be achieved using a suffix automaton. The automaton compactly represents all substrings of a string, and the number of distinct substrings can be computed from its state transitions. This approach is efficient but more complex to implement than rolling hash, which is why hashing is often preferred in interviews.

What is the best approach for Number of Distinct Substrings in a String?

The most practical approach is rolling hash (string hashing). It generates substring hashes in O(1) time while expanding each substring and stores them in a hash set to remove duplicates. This reduces the complexity to O(n^2) time compared to O(n^3) for naive substring extraction, while keeping the implementation relatively simple for interviews.

Is Number of Distinct Substrings in a String asked at Google/Amazon/Meta?

Substring uniqueness and suffix-based counting problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants often involve counting distinct substrings, repeated substrings, or substring comparisons using hashing or suffix data structures.

What data structure is used in Number of Distinct Substrings in a String?

Common data structures include hash sets for storing substring hashes, rolling hash arrays for efficient substring hashing, and advanced structures like tries, suffix arrays, or suffix automata. The rolling hash with a hash set is the most common interview-friendly combination.

What is the time complexity of Number of Distinct Substrings in a String?

The brute force method takes O(n^3) time because it generates O(n^2) substrings and copying each substring may take O(n). Using rolling hash reduces the complexity to O(n^2) since each substring hash is updated in constant time. More advanced suffix-based structures can achieve near O(n) or O(n log n).

Description Hints 4 Solution Video 18:10

1698. Number of Distinct Substrings in a String

Medium64.4% acceptance4 companiesPremium elsewhere, free here

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

A substring of a string is obtained by deleting any number of characters (possibly zero) from the front of the string and any number (possibly zero) from the back of the string.

Example 1:

Input: s = "aabbaba"
Output: 21
Explanation: The set of distinct strings is ["a","b","aa","bb","ab","ba","aab","abb","bab","bba","aba","aabb","abba","bbab","baba","aabba","abbab","bbaba","aabbab","abbaba","aabbaba"]

Example 2:

Input: s = "abcdefg"
Output: 28

Constraints:

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

Follow up: Can you solve this problem in O(n) time complexity?

Asked at 4 companies

Dunzo Intuit Uber Bloomberg

Topics

Hints open one at a time

Hint 1

Calculate the prefix hashing array for s.

Hint 2

Use the prefix hashing array to calculate the hashing value of each substring.

Hint 3

Compare the hashing values to determine the unique substrings.

Hint 4

There could be collisions if you use hashing, what about double hashing.

18:10

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"aabbaba"

Input

"abcdefg"

Your code is saved on this device.Solution