How hard is LeetCode 1698. Number of Distinct Substrings in a String?

LeetCode 1698. Number of Distinct Substrings in a String is rated Medium on LeetCode.

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

The Python solution on this page runs in O(n^3).

What is the space complexity of LeetCode 1698. Number of Distinct Substrings in a String?

The Python solution on this page uses O(n^2) auxiliary space.

What topics does LeetCode 1698. Number of Distinct Substrings in a String cover?

LeetCode 1698. Number of Distinct Substrings in a String is tagged Trie, String, Suffix Array, Hash Function and Rolling Hash on LeetCode.

Is LeetCode 1698. Number of Distinct Substrings in a String a premium problem?

Yes. LeetCode 1698. Number of Distinct Substrings in a String is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Number of Distinct Substrings in a String — LeetCode 1698 Python Solution

MediumLeetCode PremiumTrieStringSuffix ArrayHash FunctionRolling Hash

Problem: #1698
Pattern: Trie
Reading time: 2 min
Source: leetcode.com

The problem

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

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"]

Python solution

Python

class Solution:
    def countDistinct(self, s: str) -> int:
        n = len(s)
        return len({s[i:j] for i in range(n) for j in range(i + 1, n + 1)})

Complexity

Measure	Complexity
Time	O(n^3)
Space	O(n^2) auxiliary

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1698. Number of Distinct Substrings in a String is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Trie.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1698. Number of Distinct Substrings in a String?: LeetCode 1698. Number of Distinct Substrings in a String is rated Medium on LeetCode.
What is the time complexity of LeetCode 1698. Number of Distinct Substrings in a String?: The Python solution on this page runs in O(n^3).
What is the space complexity of LeetCode 1698. Number of Distinct Substrings in a String?: The Python solution on this page uses O(n^2) auxiliary space.
What topics does LeetCode 1698. Number of Distinct Substrings in a String cover?: LeetCode 1698. Number of Distinct Substrings in a String is tagged Trie, String, Suffix Array, Hash Function and Rolling Hash on LeetCode.
Is LeetCode 1698. Number of Distinct Substrings in a String a premium problem?: Yes. LeetCode 1698. Number of Distinct Substrings in a String is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.