golang 解法, 执行用时: 48 ms, 内存消耗: 3.8 MB, 提交时间: 2023-10-22 08:39:37

func equalDigitFrequency(s string) int {
	N := len(s)
	uniqSeq := map[string]struct{}{}
	for i := 0; i < N; i++ {
		charCount := [10]int{}
		maxCount := 1
		totalCount := 1
		charCount[int(s[i]-'0')] = 1
		for j := i + 1; j <= N; j++ {
			if (j-i)%totalCount == 0 && (j-i)/totalCount == maxCount {
				uniqSeq[s[i:j]] = struct{}{}
			}
			if j < N {
				idx := int(s[j] - '0')
				if charCount[idx] == 0 {
					totalCount++
				}
				charCount[idx] += 1
				if charCount[idx] > maxCount {
					maxCount = charCount[idx]
				}
			}
		}
	}
	return len(uniqSeq)
}

// hash + 暴力
func equalDigitFrequency2(s string) int {
	visited := map[string]bool{}
	check := func(a [10]int) bool {
		last := -1
		for i := 0; i < 10; i++ {
			if a[i] == 0 {
				continue
			}
			if last != -1 && a[i] != last {
				return false
			}
			last = a[i]
		}
		return true
	}
	ans := 0
	for i := 0; i < len(s); i++ {
		cur := [10]int{}
		for j := i; j < len(s); j++ {
			cur[s[j]-'0']++
			key := s[i : j+1]

			
			if check(cur) {
				if visited[key] {
					continue
				}
				visited[key] = true
				ans++
			}
		}
	}
	return ans
}

java 解法, 执行用时: 490 ms, 内存消耗: 44.2 MB, 提交时间: 2023-10-22 08:38:45

class Solution {
    public int equalDigitFrequency(String s) {
        int n = s.length();
        int[][] times = new int[n][10];//索引 数字，索引0 到 i 数字 digit 的总出现次数
        for(int i = 0; i < n; i++){
            int digit = s.charAt(i)-'0';
            for(int j = 0; j < 10; j++){
                times[i][j] = i==0?0:times[i-1][j];
            }

            times[i][digit]++;
        }
        Set<String> set = new HashSet<>();
        for(int end = 0; end < n; end++){
            int digit = s.charAt(end)-'0';
            for(int start = 0; start<=end; start++){
                //当前数字出现次数
                int time = times[end][digit]-(start==0?0:times[start-1][digit]);
                boolean isConsequent = true;
                for(int i = 0; i < 10; i++){
                    //剩余数字只能出现 0/time 次
                    int itemTime = times[end][i]-(start==0?0:times[start-1][i]);
                    if(itemTime!=0&&itemTime!=time){
                        isConsequent = false;
                    }
                }
                if(isConsequent)
                    set.add(s.substring(start,end+1));
            }
        }
        return set.size();
    }
}

python3 解法, 执行用时: 2428 ms, 内存消耗: 16.9 MB, 提交时间: 2023-10-22 08:38:14

class Solution:
 
    def equalDigitFrequency(self, s: str) -> int:
        """
        双指针+计数+集合去重
        """
        temp_num = set()
        counter = collections.defaultdict(int)
        for i in range(len(s)):
            counter[s[i]] += 1
            if s[i] not in temp_num:
                temp_num.add(s[i])
            for j in range(i + 1, len(s)):
                counter[s[j]] += 1
                if len(set(counter.values())) == 1:
                    if s[i:j + 1] not in temp_num:
                        temp_num.add(s[i:j + 1])
            counter.clear()
        return len(temp_num)

python3 解法, 执行用时: 3584 ms, 内存消耗: 17 MB, 提交时间: 2023-10-22 08:37:52

class Solution:
    def equalDigitFrequency(self, s: str) -> int:
        """Given a digit string s, return the number of unique substrings of s where every digit appears the same number of times."""

        def check(left: int, right: int) -> bool:
            """"[left,right] 这一段子串符合题意"""
            diff = set()
            for i in range(10):
                count = preSum[right + 1][i] - preSum[left][i]
                if count > 0:
                    diff.add(count)
                if len(diff) > 1:
                    return False
            return True

        n = len(s)
        preSum = [[0] * 10 for _ in range(n + 1)]

        # 预处理前缀
        for i in range(1, n + 1):
            preSum[i][ord(s[i - 1]) - ord('0')] += 1
            for j in range(10):
                preSum[i][j] += preSum[i - 1][j]

        res = set()
        # 枚举所有子串
        for i in range(n):
            for j in range(i, n):
                if check(i, j):
                    res.add(s[i : j + 1])

        return len(res)

cpp 解法, 执行用时: 52 ms, 内存消耗: 8.6 MB, 提交时间: 2023-10-22 08:37:39

const unsigned long base = 233;
class Solution {
public:
    int equalDigitFrequency(string s) {
        unordered_set<unsigned long> m;
        for(int i = 0; i < s.size(); ++i) {
            int cnts[10];
            memset(cnts, 0, sizeof(cnts));
            unsigned long cur = 0;
            int maxv = 0, maxc = 0, curc = 0;
            for(int k = i; k < s.size(); ++k) {
                cur = cur * base + (s[k] - '0') + 1;
                int cnt = ++cnts[s[k] - '0'];
                if(cnt == 1) {
                    ++curc;
                }
                if(cnt > maxv) {
                    maxv = cnt, maxc = 1;
                }
                else if(cnt == maxv) {
                    ++maxc;
                }
                if(maxc == curc) {
                    m.insert(cur);
                }
            }
        }
        return m.size();
    }
};