Skip to content

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

Thinking

Count distinct substrings whose present digits all share one frequency. \(n\le 1000\) gives \(O(n^2)\) substrings; scanning each from scratch is cubic.

Prefix counts of the ten digits give a frequency vector in \(O(1)\); we then check that the nonempty frequencies form a singleton. A set stores the substrings themselves.

Enumerate \([i,j]\) and insert \(s[i:j+1]\) when the prefix-difference test passes.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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)

 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
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;
    }
}

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

Comments