Question

2168. Unique Substrings With Equal Digit Frequency

中文文档

Description

Given a digit string s, return _the number of unique substrings of _s_ where every digit appears the same number of times._

 

Example 1:

Input: s = "1212"
Output: 5
Explanation: The substrings that meet the requirements are "1", "2", "12", "21", "1212".
Note that although the substring "12" appears twice, it is only counted once.

Example 2:

Input: s = "12321"
Output: 9
Explanation: The substrings that meet the requirements are "1", "2", "3", "12", "23", "32", "21", "123", "321".

 

Constraints:

• 1 <= s.length <= 1000
• s consists of digits.

Solutions

Solution 1

class Solution:
  def equalDigitFrequency(self, s: str) -> int:
    def check(i, j):
      v = set()
      for k in range(10):
        cnt = presum[j + 1][k] - presum[i][k]
        if cnt > 0:
          v.add(cnt)
        if len(v) > 1:
          return False
      return True

    n = len(s)
    presum = [[0] * 10 for _ in range(n + 1)]
    for i, c in enumerate(s):
      presum[i + 1][int(c)] += 1
      for j in range(10):
        presum[i + 1][j] += presum[i][j]
    vis = set(s[i : j + 1] for i in range(n) for j in range(i, n) if check(i, j))
    return len(vis)

class Solution {
  public int equalDigitFrequency(String s) {
    int n = s.length();
    int[][] presum = new int[n + 1][10];
    for (int i = 0; i < n; ++i) {
      ++presum[i + 1][s.charAt(i) - '0'];
      for (int j = 0; j < 10; ++j) {
        presum[i + 1][j] += presum[i][j];
      }
    }
    Set<String> vis = new HashSet<>();
    for (int i = 0; i < n; ++i) {
      for (int j = i; j < n; ++j) {
        if (check(i, j, presum)) {
          vis.add(s.substring(i, j + 1));
        }
      }
    }
    return vis.size();
  }

  private boolean check(int i, int j, int[][] presum) {
    Set<Integer> v = new HashSet<>();
    for (int k = 0; k < 10; ++k) {
      int cnt = presum[j + 1][k] - presum[i][k];
      if (cnt > 0) {
        v.add(cnt);
      }
      if (v.size() > 1) {
        return false;
      }
    }
    return true;
  }
}

func equalDigitFrequency(s string) int {
  n := len(s)
  presum := make([][]int, n+1)
  for i := range presum {
    presum[i] = make([]int, 10)
  }
  for i, c := range s {
    presum[i+1][c-'0']++
    for j := 0; j < 10; j++ {
      presum[i+1][j] += presum[i][j]
    }
  }
  check := func(i, j int) bool {
    v := make(map[int]bool)
    for k := 0; k < 10; k++ {
      cnt := presum[j+1][k] - presum[i][k]
      if cnt > 0 {
        v[cnt] = true
      }
      if len(v) > 1 {
        return false
      }
    }
    return true
  }
  vis := make(map[string]bool)
  for i := 0; i < n; i++ {
    for j := i; j < n; j++ {
      if check(i, j) {
        vis[s[i:j+1]] = true
      }
    }
  }
  return len(vis)
}