We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Unique Substrings With Equal Digit Frequency

Number: 2303

Difficulty: Medium

Paid? Yes

Companies: Expedia

Problem Description

Given a digit string s, return the number of unique substrings of s where every digit that appears in the substring has the same frequency. Note that a substring is a contiguous sequence of characters, and duplicate substrings should be counted only once.

Key Insights

  • All substrings are generated using a pair of indices (i, j) representing the start and end of the substring.
  • For a substring to be valid, every digit that appears must appear the same number of times. For example, a substring with counts { '1': 2, '2': 2 } is valid.
  • Single-digit substrings are automatically valid.
  • A hash set is used to store unique valid substrings.
  • Use a frequency counter that can be efficiently updated as the substring extends.

Space and Time Complexity

Time Complexity: O(n^2 * k) where n is the length of s and k is the number of digits (bounded by 10), since for each substring we verify the frequency condition in O(k). Space Complexity: O(n^2 * n) in the worst case (for storing all unique substrings), though typically it will be much less due to repeated substrings and the limited set of digits.

Solution

We solve the problem by iterating over all possible substrings of s. For each substring, we maintain a frequency count of digits encountered so far. After updating the frequency for each new character, we check if the set of non-zero frequency counts has a single unique value. If yes, the substring meets the criteria and is added to a hash set to ensure uniqueness.

Key data structures and steps:

  • Use two nested loops to generate all substrings.
  • Use an array or dictionary (depending on language) of size 10 (for digits '0'-'9') to update the frequency count while extending the substring.
  • Check condition: collect frequencies for which count > 0 into a set and verify that its size is 1.
  • After iterating through all candidates, return the size of the set as the count of unique substrings qualifying the criteria.

This approach leverages the small constant (10 digits) to keep the frequency check efficient, and the hash set to avoid counting the same substring more than once.

Code Solutions

# Python solution with line-by-line comments
class Solution:
    def uniqueDigitSubstrings(self, s: str) -> int:
        # Set to keep track of valid unique substrings
        valid_substrings = set()
        n = len(s)
        
        # Iterate over all possible starting points of substring
        for i in range(n):
            # Initialize digit frequency count for substring starting at index i
            freq = [0] * 10  # For digits '0'-'9'
            # Expand substring from index i to j
            for j in range(i, n):
                digit = int(s[j])
                freq[digit] += 1
                
                # Gather counts of digits that have appeared (non zero frequencies)
                current_counts = {count for count in freq if count > 0}
                # Check if all digits present have the same count
                if len(current_counts) == 1:
                    valid_substrings.add(s[i:j+1])
                    
        return len(valid_substrings)

# Example usage:
# sol = Solution()
# print(sol.uniqueDigitSubstrings("1212"))
← Back to All Questions