Problem

Given a digit string s, return _the number ofunique substrings of _s where every digit appears the same number of times.

Examples

Example 1:

1
2
3
4

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:

1
2
3

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.

Solution

Method 1 – Brute Force with Hashing

Intuition

We can check all substrings and use a hash set to count unique ones where all digits appear the same number of times. For each substring, count digit frequencies and check if all nonzero counts are equal.

Approach

  1. For each substring, count digit frequencies.
  2. If all nonzero frequencies are equal, add the substring to a set.
  3. Return the size of the set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import java.util.*;
class Solution {
    public int equalDigitFrequency(String s) {
        Set<String> set = new HashSet<>();
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int[] cnt = new int[10];
            for (int j = i; j < n; ++j) {
                cnt[s.charAt(j) - '0']++;
                int freq = 0;
                boolean ok = true;
                for (int c : cnt) {
                    if (c > 0) {
                        if (freq == 0) freq = c;
                        else if (freq != c) { ok = false; break; }
                    }
                }
                if (ok) set.add(s.substring(i, j + 1));
            }
        }
        return set.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def equalDigitFrequency(s):
    seen = set()
    n = len(s)
    for i in range(n):
        cnt = [0]*10
        for j in range(i, n):
            cnt[int(s[j])] += 1
            freq = 0
            ok = True
            for c in cnt:
                if c > 0:
                    if freq == 0:
                        freq = c
                    elif freq != c:
                        ok = False
                        break
            if ok:
                seen.add(s[i:j+1])
    return len(seen)

Complexity

  • ⏰ Time complexity: O(n^3) — O(n^2) substrings, O(1) for digit check, O(n) for substring hash.
  • 🧺 Space complexity: O(n^2) — For storing all unique substrings.