Skip to content

1698. Number of Distinct Substrings in a String 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
 public:
  int countDistinct(string s) {
    const int n = s.length();
    int ans = 0;
    vector<long> pow(n + 1);     // pow[i] := kBase^i
    vector<long> hashes(n + 1);  // hashes[i] := the hash of s[0..i)

    pow[0] = 1;
    for (int i = 1; i <= n; ++i) {
      pow[i] = pow[i - 1] * kBase % kMod;
      hashes[i] = (hashes[i - 1] * kBase + val(s[i - 1])) % kMod;
    }

    for (int length = 1; length <= n; ++length) {
      unordered_set<int> seen;
      for (int i = 0; i + length <= n; ++i)
        seen.insert(getHash(i, i + length, hashes, pow));
      ans += seen.size();
    }

    return ans;
  }

 private:
  static constexpr int kBase = 26;
  static constexpr int kMod = 1'000'000'007;

  // Returns the hash of s[l..r).
  long getHash(int l, int r, const vector<long>& hashes,
               const vector<long>& pow) {
    const long hash = (hashes[r] - hashes[l] * pow[r - l]) % kMod;
    return hash < 0 ? hash + kMod : hash;
  }

  constexpr int val(char c) {
    return c - 'a';
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  public int countDistinct(String s) {
    final int n = s.length();
    int ans = 0;
    long[] pow = new long[n + 1];    // pow[i] := kBase^i
    long[] hashes = new long[n + 1]; // hashes[i] := the hash of s[0..i)

    pow[0] = 1;
    for (int i = 1; i <= n; ++i) {
      pow[i] = pow[i - 1] * kBase % kMod;
      hashes[i] = (hashes[i - 1] * kBase + val(s.charAt(i - 1))) % kMod;
    }

    for (int length = 1; length <= n; ++length) {
      Set<Long> seen = new HashSet<>();
      for (int i = 0; i + length <= n; ++i)
        seen.add(getHash(i, i + length, hashes, pow));
      ans += seen.size();
    }

    return ans;
  }

  private static final int kBase = 26;
  private static final int kMod = 1_000_000_007;

  // Returns the hash of s[l..r).
  private long getHash(int l, int r, long[] hashes, long[] pow) {
    final long hash = (hashes[r] - hashes[l] * pow[r - l]) % kMod;
    return hash < 0 ? hash + kMod : hash;
  }

  private int val(char c) {
    return c - 'a';
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
  def countDistinct(self, s: str) -> int:
    kBase = 26
    kMod = 1_000_000_007

    n = len(s)
    ans = 0
    pow = [1] + [0] * n     # pow[i] := kBase^i
    hashes = [0] * (n + 1)  # hashes[i] := the hash of s[0..i)

    def val(c: str) -> int:
      return ord(c) - ord('a')

    for i in range(1, n + 1):
      pow[i] = pow[i - 1] * kBase % kMod
      hashes[i] = (hashes[i - 1] * kBase + val(s[i - 1])) % kMod

    def getHash(l: int, r: int) -> int:
      """Returns the hash of s[l..r)."""
      hash = (hashes[r] - hashes[l] * pow[r - l]) % kMod
      return hash + kMod if hash < 0 else hash

    for length in range(1, n + 1):
      seen = set()
      for i in range(n - length + 1):
        seen.add(getHash(i, i + length))
      ans += len(seen)

    return ans