5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 17:I[4821,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 18:I[2647,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 1a:I[7912,["874","static/chunks/874-64ff3adb125f84b1.js","269","static/chunks/269-5f9235f83b944543.js","222","static/chunks/222-e37d1f81e0d6d2ef.js","934","static/chunks/app/cs/problems/%5Bslug%5D/page-935d3f20891d8cfc.js"],"default"] 19:Tbd3,

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:

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.

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

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

Code

[{"language":"Java","code":"import java.util.*;\nclass Solution {\n    public int equalDigitFrequency(String s) {\n        Set<String> set = new HashSet<>();\n        int n = s.length();\n        for (int i = 0; i < n; ++i) {\n            int[] cnt = new int[10];\n            for (int j = i; j < n; ++j) {\n                cnt[s.charAt(j) - '0']++;\n                int freq = 0;\n                boolean ok = true;\n                for (int c : cnt) {\n                    if (c > 0) {\n                        if (freq == 0) freq = c;\n                        else if (freq != c) { ok = false; break; }\n                    }\n                }\n                if (ok) set.add(s.substring(i, j + 1));\n            }\n        }\n        return set.size();\n    }\n}","lang":"java"},{"language":"Python","code":"def equalDigitFrequency(s):\n    seen = set()\n    n = len(s)\n    for i in range(n):\n        cnt = [0]*10\n        for j in range(i, n):\n            cnt[int(s[j])] += 1\n            freq = 0\n            ok = True\n            for c in cnt:\n                if c > 0:\n                    if freq == 0:\n                        freq = c\n                    elif freq != c:\n                        ok = False\n                        break\n            if ok:\n                seen.add(s[i:j+1])\n    return len(seen)","lang":"python"}]

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.

8:["$","div",null,{"className":"max-w-7xl mx-auto px-4 py-8","children":[["$","header",null,{"className":"mb-8 pb-4","children":[["$","div",null,{"className":"flex flex-wrap items-start justify-between gap-4","children":[["$","h1",null,{"className":"text-4xl font-bold text-gray-900 dark:text-gray-100","chil

Related Tags