Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2168.html

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.

• Java
• Python
• Go

• 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