Welcome to Subscribe On Youtube

2168. Unique Substrings With Equal Digit Frequency

Description

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.

Solutions

  • class Solution {
        public int equalDigitFrequency(String s) {
            int n = s.length();
            int[][] presum = new int[n + 1][10];
            for (int i = 0; i < n; ++i) {
                ++presum[i + 1][s.charAt(i) - '0'];
                for (int j = 0; j < 10; ++j) {
                    presum[i + 1][j] += presum[i][j];
                }
            }
            Set<String> vis = new HashSet<>();
            for (int i = 0; i < n; ++i) {
                for (int j = i; j < n; ++j) {
                    if (check(i, j, presum)) {
                        vis.add(s.substring(i, j + 1));
                    }
                }
            }
            return vis.size();
        }
    
        private boolean check(int i, int j, int[][] presum) {
            Set<Integer> v = new HashSet<>();
            for (int k = 0; k < 10; ++k) {
                int cnt = presum[j + 1][k] - presum[i][k];
                if (cnt > 0) {
                    v.add(cnt);
                }
                if (v.size() > 1) {
                    return false;
                }
            }
            return true;
        }
    }
    
  • class Solution:
        def equalDigitFrequency(self, s: str) -> int:
            def check(i, j):
                v = set()
                for k in range(10):
                    cnt = presum[j + 1][k] - presum[i][k]
                    if cnt > 0:
                        v.add(cnt)
                    if len(v) > 1:
                        return False
                return True
    
            n = len(s)
            presum = [[0] * 10 for _ in range(n + 1)]
            for i, c in enumerate(s):
                presum[i + 1][int(c)] += 1
                for j in range(10):
                    presum[i + 1][j] += presum[i][j]
            vis = set(s[i : j + 1] for i in range(n) for j in range(i, n) if check(i, j))
            return len(vis)
    
    
  • func equalDigitFrequency(s string) int {
    	n := len(s)
    	presum := make([][]int, n+1)
    	for i := range presum {
    		presum[i] = make([]int, 10)
    	}
    	for i, c := range s {
    		presum[i+1][c-'0']++
    		for j := 0; j < 10; j++ {
    			presum[i+1][j] += presum[i][j]
    		}
    	}
    	check := func(i, j int) bool {
    		v := make(map[int]bool)
    		for k := 0; k < 10; k++ {
    			cnt := presum[j+1][k] - presum[i][k]
    			if cnt > 0 {
    				v[cnt] = true
    			}
    			if len(v) > 1 {
    				return false
    			}
    		}
    		return true
    	}
    	vis := make(map[string]bool)
    	for i := 0; i < n; i++ {
    		for j := i; j < n; j++ {
    			if check(i, j) {
    				vis[s[i:j+1]] = true
    			}
    		}
    	}
    	return len(vis)
    }
    

All Problems

All Solutions