# 2168. Unique Substrings With Equal Digit Frequency
###### tags: `Leetcode` `Medium` `Rolling Hash`
Link: https://leetcode.com/problems/unique-substrings-with-equal-digit-frequency/description/
## 思路
由于字符串长度最多才1000
所以我们可以花$O(N^2)$的时间遍历所有substring是没有问题的
我们可以用rolling hash的方法找一共有多少个unique substring 不然把所有substring都存在hash里面空间复杂度有点高
为了避免将"012"和"12"都哈希成同一个编码，我们可以将十进制的编码规则改为十一进制，这样字符0也会被编码。即

for (int j=i; j<n; j++)
  hash = hash*11+(s[j]-'0'+1);

## Code

class Solution {
    public int equalDigitFrequency(String s) {
        Set<Long> set = new HashSet<>();
        int n = s.length();
        int[] cnt = new int[10];
        for(int i=0; i<n; i++){
            Arrays.fill(cnt, -1);
            long hash = 0;
            for(int j=i; j<n; j++){
                cnt[s.charAt(j)-'0']++;
                hash = hash*11+s.charAt(j)-'0'+1;
                int freq = -1;
                boolean flag = true;
                for(int k=0; k<10; k++){
                    if(cnt[k]==-1) continue;
                    if(freq==-1) freq = cnt[k];
                    if(cnt[k]!=freq){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    set.add(hash);
                }
            }
        }
        return set.size();
    }
}