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
class Solution {
 public:
  int equalDigitFrequency(string s) {
    const string_view sv(s);
    unordered_set<int> seen;

    for (int i = 0; i < s.length(); ++i)
      for (int j = i; j < s.length(); ++j)
        if (isUnique(sv.substr(i, j - i + 1)))
          seen.insert(getRollingHash(sv.substr(i, j - i + 1)));

    return seen.size();
  }

 private:
  static constexpr int power = 11;
  static constexpr int kMod = 1'000'000'007;

  bool isUnique(const string_view& sv) {
    vector<int> count(10);
    int unique = 0;
    for (const char c : sv)
      if (++count[c - '0'] == 1)
        ++unique;
    const int maxCount = ranges::max(count);
    return maxCount * unique == sv.length();
  }

  int getRollingHash(const string_view& sv) {
    long hash = 0;
    for (const char c : sv)
      hash = (hash * power + val(c)) % kMod;
    return hash;
  }

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

 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 equalDigitFrequency(String s) {
    Set<Integer> seen = new HashSet<>();

    for (int i = 0; i < s.length(); ++i)
      for (int j = i; j < s.length(); ++j)
        if (isUnique(s, i, j))
          seen.add(getRollingHash(s, i, j));

    return seen.size();
  }

  private static final int power = 11;
  private static final int kMod = 1_000_000_007;

  private boolean isUnique(final String s, int i, int j) {
    int[] count = new int[10];
    int unique = 0;
    for (int k = i; k <= j; ++k)
      if (++count[s.charAt(k) - '0'] == 1)
        ++unique;
    final int maxCount = Arrays.stream(count).max().getAsInt();
    return maxCount * unique == j - i + 1;
  }

  private int getRollingHash(final String s, int i, int j) {
    long hash = 0;
    for (int k = i; k <= j; ++k)
      hash = (hash * power + val(s.charAt(k))) % kMod;
    return (int) hash;
  }

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

 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
class Solution:
  def equalDigitFrequency(self, s: str) -> int:
    power = 11
    kMod = 1_000_000_007
    seen = set()

    def isUnique(s: str, i: int, j: int) -> bool:
      count = [0] * 10
      unique = 0
      for k in range(i, j + 1):
        count[ord(s[k]) - ord('0')] += 1
        if count[ord(s[k]) - ord('0')] == 1:
          unique += 1
      maxCount = max(count)
      return maxCount * unique == j - i + 1

    def getRollingHash(s: str, i: int, j: int) -> int:
      hash = 0
      for k in range(i, j + 1):
        hash = (hash * power + val(s[k])) % kMod
      return hash

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

    for i in range(len(s)):
      for j in range(i, len(s)):
        if isUnique(s, i, j):
          seen.add(getRollingHash(s, i, j))

    return len(seen)