##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2168.html

# 2168. Unique Substrings With Equal Digit Frequency (Medium)

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.

Companies:
Expedia

Related Topics:
Hash Table, String, Rolling Hash, Counting, Hash Function

Similar Questions:

## Solution 1.

• 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) {
}
if (v.size() > 1) {
return false;
}
}
return true;
}
}

• 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:
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)


• 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)
}