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 <= 2500s consists of digits from '0' to '9'.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:
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:
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)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:
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)| Case | How to Handle |
|---|---|
| The string has one character | That character is good, so the result is one. |
| Every character is the same digit | Each distinct length forms one good string, so the result equals the length. |
| The same digits appear in two different orders | Those are different strings, and both are counted when each one has equal frequencies. |
| One digit appears more often than another inside a window | That window is rejected. |
| The whole string has equal frequencies | The full string is stored together with every shorter good piece. |
| The same good string occurs in two places | The collection keeps a single copy of that string. |