Skip to content

2168. Unique Substrings With Equal Digit Frequency 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
 public:
  int equalDigitFrequency(string s) {
    vector<vector<int>> counts;  // counts[i] := the counter map of s[0..i]
    vector<int> count(10);
    vector<long> pows{1};  // pows[i] := kBase^i % kHash
    // hash[i] = the hash of the first i letters of s, where hash[i] =
    // (26^(i - 1) * s[0] + 26^(i - 2) * s[1] + ... + s[i - 1]) % kHash
    vector<long> hash{0};
    unordered_set<int> seen;

    for (const char c : s) {
      ++count[c - '0'];
      counts.push_back(count);
      pows.push_back(pows.back() * kBase % kHash);
      hash.push_back((hash.back() * kBase + val(c)) % kHash);
    }

    for (int i = 0; i < s.length(); ++i)
      for (int j = i; j < s.length(); ++j)
        if (isSameFreq(counts, i, j))
          seen.insert(getRollingHash(i, j + 1, hash, pows));

    return seen.size();
  }

 private:
  static constexpr int kMax = 1001;
  static constexpr int kBase = 11;
  static constexpr int kHash = 1'000'000'007;

  static constexpr int val(char c) {
    return c - '0' + 1;
  }

  // Returns true if s[i..j] has the same digit frequency.j
  bool isSameFreq(const vector<vector<int>>& counts, int i, int j) {
    vector<int> count = counts[j];
    if (i > 0)
      for (int num = 0; num < 10; ++num)
        count[num] -= counts[i - 1][num];
    return equalFreq(count);
  }

  bool equalFreq(const vector<int>& count) {
    int minfreq = kMax;
    int maxfreq = 0;
    for (const int freq : count)
      if (freq > 0) {
        minfreq = min(minfreq, freq);
        maxfreq = max(maxfreq, freq);
      }
    return minfreq == maxfreq;
  }

  // Returns the rolling hash of s[l..r).
  int getRollingHash(int l, int r, const vector<long>& hash,
                     const vector<long>& pows) {
    const long h = (hash[r] - hash[l] * pows[r - l]) % kHash;
    return h < 0 ? h + kHash : h;
  }
};

 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class Solution {
  public int equalDigitFrequency(String s) {
    int[][] counts = new int[n][]; // counts[i] := the counter map of s[0..i]
    int[] count = new int[10];
    long[] pows = new long[n + 1]; // pows[i] := kBase^i % kHash
    // hash[i] = the hash of the first i letters of s, where hash[i] =
    // (26^(i - 1) * s[0] + 26^(i - 2) * s[1] + ... + s[i - 1]) % kHash
    long[] hash = new long[n + 1];
    Set<Integer> seen = new HashSet<>();

    pows[0] = 1;

    for (int i = 0; i < n; ++i) {
      ++count[s.charAt(i) - '0'];
      counts[i] = count.clone();
      pows[i + 1] = pows[i] * kBase % kHash;
      hash[i + 1] = (hash[i] * kBase + val(s.charAt(i))) % kHash;
    }

    for (int i = 0; i < n; ++i)
      for (int j = i; j < n; ++j)
        if (isSameFreq(counts, i, j))
          seen.add(getRollingHash(i, j + 1, hash, pows));

    return seen.size();
  }

  private static final int kMax = 1001;
  private static final int kBase = 11;
  private static final int kHash = 1_000_000_007;

  private static int val(char c) {
    return c - '0' + 1;
  }

  // Returns true if s[i..j] has the same digit frequency.j
  private boolean isSameFreq(int[][] counts, int i, int j) {
    int[] count = counts[j].clone();
    if (i > 0)
      for (int num = 0; num < 10; ++num)
        count[num] -= counts[i - 1][num];
    return equalFreq(count);
  }

  private boolean equalFreq(int[] count) {
    int minfreq = kMax;
    int maxfreq = 0;
    for (final int freq : count)
      if (freq > 0) {
        minfreq = Math.min(minfreq, freq);
        maxfreq = Math.max(maxfreq, freq);
      }
    return minfreq == maxfreq;
  }

  // Returns the rolling hash of s[l..r).
  private int getRollingHash(int l, int r, long[] hash, long[] pows) {
    final long h = (hash[r] - hash[l] * pows[r - l]) % kHash;
    return (int) (h < 0 ? h + kHash : h);
  }
}

 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
class Solution:
  def equalDigitFrequency(self, s: str) -> int:
    kBase = 11
    kHash = 1_000_000_007
    counts: list[dict] = []  # counts[i] := the counter map of s[0..i]
    count = collections.Counter()
    pows = [1]  # pows[i] := kBase^i % kHash
    # hash[i] = the hash of the first i letters of s, where hash[i] =
    # (26^(i - 1) * s[0] + 26^(i - 2) * s[1] + ... + s[i - 1]) % kHash
    hash = [0]

    def val(c: str) -> int:
      return int(c) + 1

    for c in s:
      count[c] += 1
      counts.append(count.copy())
      pows.append(pows[-1] * kBase % kHash)
      hash.append((hash[-1] * kBase + val(c)) % kHash)

    def getRollingHash(l: int, r: int) -> int:
      """Returns the rolling hash of s[l..r)."""
      h = (hash[r] - hash[l] * pows[r - l]) % kHash
      return h + kHash if h < 0 else h

    return len({getRollingHash(i, j + 1)
                for i in range(len(s))
                for j in range(i, len(s))
                if self._isSameFreq(counts, i, j)})

  def _isSameFreq(self, counts: list[dict], i: int, j: int) -> bool:
    count = counts[j].copy()
    if i > 0:
      for c, freq in counts[i - 1].items():
        count[c] -= freq
        if count[c] == 0:
          del count[c]
    return min(count.values()) == max(count.values())