1698. Number of Distinct Substrings in a String

1698. Number of Distinct Substrings in a String (Medium)

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?

Companies:
Intuit, Dunzo

Related Topics:
String, Trie, Rolling Hash, Suffix Array, Hash Function

Solution 1. Rabin Karp

// OJ: https://leetcode.com/problems/number-of-distinct-substrings-in-a-string/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
    int count(string &s, int len) {
        unsigned long long d = 1099511628211, h = 0, p = 1;
        unordered_set<unsigned long long> seen;
        for (int i = 0; i < s.size(); ++i) {
            h = h * d + s[i];
            if (i < len) p *= d;
            else h -= s[i - len] * p;
            if (i >= len - 1) seen.insert(h);
        }
        return seen.size();
    }
public:
    int countDistinct(string s) {
        int ans = 0;
        for (int len = 1; len <= s.size(); ++len) ans += count(s, len);
        return ans;
    }
};

Solution 2. Rabin Karp with Prefix Hash Array

// OJ: https://leetcode.com/problems/number-of-distinct-substrings-in-a-string/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int countDistinct(string s) {
        unsigned long long d = 1099511628211, h[501] = {}, p[501] = {1}, N = s.size();
        for (int i = 0; i < N; ++i) {
            p[i + 1] = p[i] * d;
            h[i + 1] = h[i] * d + s[i];
        }
        unordered_set<unsigned long long> seen;
        for (int len = 1; len <= N; ++len) {
            for (int i = 0; i + len <= N; ++i) {
                seen.insert(h[i + len] - h[i] * p[len]);
            }
        }
        return seen.size();
    }
};