2168

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:

• Number of Equal Count Substrings (Medium)
• Substrings That Begin and End With the Same Letter (Medium)

Solution 1.

// OJ: https://leetcode.com/problems/unique-substrings-with-equal-digit-frequency/
// Author: github.com/lzl124631x
// Time: O(N^3)
// Space: O(N^2)
class Solution {
public:
    int equalDigitFrequency(string s) {
        int N = s.size();
        unordered_set<string> ans;
        for (int i = 0; i < N; ++i) {
            int cnt[10] = {};
            for (int j = i; j < N; ++j) {
                cnt[s[j] - '0']++;
                int k = 0, c = -1;
                for (; k < 10; ++k) {
                    if (cnt[k] == 0) continue;
                    if (c == -1) c = cnt[k];
                    if (cnt[k] != c) break;
                }
                if (k == 10) ans.insert(s.substr(i, j - i + 1));
            }
        }
        return ans.size();
    }
};

Solution 2. Rabin Karp

// OJ: https://leetcode.com/problems/unique-substrings-with-equal-digit-frequency/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N^2)
class Solution {
public:
    int equalDigitFrequency(string s) {
        unordered_set<int> ans;
        for (int i = 0, N = s.size(); i < N; ++i) {
            long long cnt[11] = {}, unique = 0, mxCnt = 0, hash = 0;
            for (int j = i; j < N; ++j) {
                int d = s[j] - '0';
                mxCnt = max(mxCnt, ++cnt[d]);
                unique += cnt[d] == 1;
                hash = (hash * 11 + d + 1) % 1000000007;
                if (mxCnt * unique == j - i + 1) ans.insert(hash);
            }
        }
        return ans.size();
    }
};