Taro Logo

Unique Substrings With Equal Digit Frequency

Medium
Asked by:
Profile picture
14 views
Topics:
ArraysStrings

Given a string s consisting of digits from '0' to '9'.

A string is called good if the frequency of each digit present in the string is the same.

Return the number of unique good substrings of s.

Example 1:

Input: s = "1212"
Output: 5
Explanation: The good substrings are "1", "2", "12", "21", "1212".
Note that "12" and "21" are different substrings, but they are equal as strings, so they are only counted once in the set of unique good substrings.

Example 2:

Input: s = "112233"
Output: 7
Explanation: The good substrings are "1", "11", "2", "22", "3", "33", "112233".

Example 3:

Input: s = "111"
Output: 3
Explanation: The good substrings are "1", "11", "111".

Constraints:

  • 1 <= s.length <= 2500
  • s consists of digits from '0' to '9'.

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Are digits that do not appear ignored, so only digits that occur must share one frequency?
  2. Are two copies of the same characters counted once even when they sit in different places?
  3. Is a single digit always a good substring?
  4. May the shared frequency be any positive count, including counts greater than one?
  5. Is the input made only of digit characters?

Brute Force Solution

Approach

Every substring is built from a start index and an end index. The characters of that substring are counted one by one, and the substring is kept when those counts all have the same value. A set stores the text itself, so repeated copies of the same good string contribute only once.

Here's how the algorithm would work step-by-step:

  1. Create an empty set of good strings.
  2. Choose every start index and every end index at or after it.
  3. Copy the characters between those endpoints.
  4. Count how often each digit appears in that copy.
  5. Collect the distinct count values.
  6. Add the substring when exactly one count value is present.
  7. Return the number of strings stored in the set.

Code Implementation

def unique_substrings_equal_digit_frequency(input_string):
    unique_special_substrings = set()

    # Iterate through all possible starting positions of a substring.
    for start_index in range(len(input_string)):
        # Iterate through all possible ending positions for the substring starting at start_index.
        for end_index in range(start_index, len(input_string)):
            current_substring = input_string[start_index : end_index + 1]
            digit_frequencies = {}

            for digit in current_substring:
                digit_frequencies[digit] = digit_frequencies.get(digit, 0) + 1

            # We must verify if the frequency of all present digits is the same.
            if digit_frequencies:
                # Use a set to find the number of unique frequency counts.
                frequency_values = set(digit_frequencies.values())
                if len(frequency_values) == 1:
                    unique_special_substrings.add(current_substring)

    # The final count is the number of unique substrings that met the condition.
    return len(unique_special_substrings)

Big(O) Analysis

Time Complexity
O(n^3) – Let n be the length of the string. There are O(n^2) pairs of endpoints, and each pair names one substring. Counting the digits scans every character of that substring, and the lengths of all substrings add up to a cubic total. Building each substring copies its characters, while comparing the finished counts only looks at the distinct digits. The total time is O(n^3).
Space Complexity
O(n^2) – The set stores each distinct good string once. A string of length n has O(n^2) substrings, so the set holds at most that many entries. The frequency map for the current substring is discarded before the next one is counted. A few indexes are reused. The extra memory is dominated by the stored strings and is O(n^2) entries.

Optimal Solution

Approach

Windows still begin at every index, but the digit counts grow as the right end moves instead of being recounted from scratch. A window is good when every digit that has appeared has the same count as the first distinct digit in that window. Qualifying windows are copied into a set, and the size of that set is the answer.

Here's how the algorithm would work step-by-step:

  1. Create an empty set for the good strings that are found.
  2. Choose each possible start index.
  3. Clear ten digit counts and the list of digits seen from that start.
  4. Extend the end index one character at a time and add one to that digit's count.
  5. Remember a digit the first time it appears in the window.
  6. Accept the window when every seen digit has the same count.
  7. Copy each accepted window into the set and return the set size.

Code Implementation

def count_unique_substrings_with_equal_digit_frequency(input_string):
    # Using a set ensures that we only store and count unique substrings found.
    found_unique_substrings = set()
    string_length = len(input_string)

    # This outer loop iterates through every possible starting position for a substring.
    for start_index in range(string_length):
        digit_frequency_counts = [0] * 10
        distinct_digits_in_substring = set()

        for end_index in range(start_index, string_length):
            current_character = input_string[end_index]
            digit_value = int(current_character)
            digit_frequency_counts[digit_value] += 1
            distinct_digits_in_substring.add(digit_value)

            # This check determines if the substring has the equal frequency property.
            first_digit_in_set = next(iter(distinct_digits_in_substring))
            target_frequency = digit_frequency_counts[first_digit_in_set]

            all_digits_have_equal_frequency = True
            for digit in distinct_digits_in_substring:
                if digit_frequency_counts[digit] != target_frequency:
                    all_digits_have_equal_frequency = False
                    break
            
            if all_digits_have_equal_frequency:
                # A valid substring is found, so we add it to our collection of unique finds.
                current_substring = input_string[start_index:end_index + 1]
                found_unique_substrings.add(current_substring)
    
    return len(found_unique_substrings)

Big(O) Analysis

Time Complexity
O(n^2) – Each start index is paired with each later end index, so the nested scan visits O(n^2) windows. Extending a window updates one digit count and then compares at most ten seen digits, which is constant work per window. The decision for every window is therefore quadratic. Copying an accepted window into the set takes time proportional to its length, and a string where every window qualifies adds a further linear factor on those copies. The frequency decisions themselves are O(n^2).
Space Complexity
O(n^2) – The set of unique good strings holds at most one entry for every distinct substring, and there are O(n^2) substrings. For each start, ten counts and a short list of seen digits are reused as the window grows. Those arrays do not depend on the length beyond the ten digits. The input string is read in place. The extra memory is O(n^2) because of the set.

Edge Cases

The string has one character
How to Handle:
That character is good, so the result is one.
Every character is the same digit
How to Handle:
Each distinct length forms one good string, so the result equals the length.
The same digits appear in two different orders
How to Handle:
Those are different strings, and both are counted when each one has equal frequencies.
One digit appears more often than another inside a window
How to Handle:
That window is rejected.
The whole string has equal frequencies
How to Handle:
The full string is stored together with every shorter good piece.
The same good string occurs in two places
How to Handle:
The collection keeps a single copy of that string.