Coding Daily

Problem Description

Given a string s consisting of digits, return the number of unique substrings where each digit occurs with equal frequency. A substring is a contiguous sequence of characters within the string.

Example:

Input: s = "12121"
Output: 5
Explanation:
The substrings that meet the requirements are '1', '2', '12', '21', '1212'
where '12' and '21' appear 2 times in s but they are counted only once.
'121', '12121' do not meet the requirement because '1' and '2' do not occur the same number of times.

Solution Code

import java.util.HashSet;
import java.util.Set;

public class Solution {
    /**
     * @param s: A string
     * @return: number of unique substrings
     */
    public int equalDigitFrequency(String s) {
        int n = s.length();
        Set<String> uniqueSubstrings = new HashSet<>();
        
        for (int i = 0; i < n; i++) {
            int[] count = new int[10]; // Count frequency of digits 0-9
            int maxFreq = 0;
            int uniqueDigits = 0;
            
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                if (count[c - '0'] == 0) {
                    uniqueDigits++;
                }
                count[c - '0']++;
                maxFreq = Math.max(maxFreq, count[c - '0']);
                
                // Check if all digits in the substring have the same frequency
                if (maxFreq * uniqueDigits == (j - i + 1)) {
                    uniqueSubstrings.add(s.substring(i, j + 1));
                }
            }
        }
        
        return uniqueSubstrings.size();
    }
}

Approach Name

Sliding Window with Frequency Counting

Intuition

The problem requires finding all unique substrings where each digit occurs with equal frequency. We can achieve this by using a sliding window approach to consider all possible substrings and maintaining a frequency count of digits within each window. If the frequency of all digits in the window is the same, we add the substring to a set to ensure uniqueness.

Algorithm

Initialize a Set:
- Use a set to store unique substrings that meet the criteria.
Sliding Window:
- Iterate through the string using a nested loop. The outer loop fixes the starting index of the substring, and the inner loop extends the substring to the end of the string.
- For each substring, maintain a frequency count of digits using an array.
Check Frequency Equality:
- For each substring, calculate the maximum frequency of any digit and the number of unique digits.
- If the product of the maximum frequency and the number of unique digits equals the length of the substring, then all digits in the substring occur with the same frequency.
Store Unique Substrings:
- Add valid substrings to the set to ensure uniqueness.
Return the Count:
- The size of the set is the number of unique substrings that meet the criteria.

Complexity Analysis

Time Complexity: O(n^2), where n is the length of the string. The nested loop structure results in a quadratic time complexity.
Space Complexity: O(n^2), in the worst case, the set could store all possible substrings, leading to a quadratic space complexity.

Medium - 🔒 2067. Number of Equal Count Substrings
Medium - 🔒 2083. Substrings That Begin and End With the Same Letter

Medium - 3807. Unique Substrings with Equal Digit Frequency

2083. Unique Substrings With Equal Digit Frequency