Problem Description

You are given a string s that consists only of digits (0-9). Your task is to find the number of unique substrings where every digit that appears in the substring appears the same number of times.

For example:

• In substring "112233", digits 1, 2, and 3 each appear exactly 2 times - this is valid
• In substring "1123", digit 1 appears 2 times while digits 2 and 3 appear 1 time each - this is invalid
• In substring "111", only digit 1 appears and it appears 3 times - this is valid

The solution uses a prefix sum approach to efficiently count digit frequencies in any substring. The presum array tracks cumulative counts of each digit (0-9) up to each position. For each possible substring from index i to j, the check function verifies if all present digits have the same frequency by:

1. Calculating the count of each digit in the substring using prefix sums
2. Collecting all non-zero counts into a set
3. Returning true if the set has at most 1 unique value (meaning all digits appear the same number of times)

Finally, all valid substrings are stored in a set to ensure uniqueness, and the size of this set is returned as the answer.

Intuition

The key insight is that we need to check every possible substring to see if it satisfies our condition (all digits appear the same number of times). A brute force approach would generate each substring and count digit frequencies, but this involves repeated counting of the same characters.

To optimize this, we can observe that counting digit frequencies in a substring s[i:j+1] is essentially finding the difference between cumulative counts at position j+1 and position i. This is similar to how we use prefix sums to find range sums efficiently.

For each position in the string, we maintain a running count of how many times each digit (0-9) has appeared up to that point. This gives us a 2D prefix sum array where presum[i][d] represents the count of digit d in the substring s[0:i].

To check if a substring s[i:j+1] has all digits appearing the same number of times, we:

1. Calculate the frequency of each digit using presum[j+1][k] - presum[i][k]
2. Collect all non-zero frequencies (digits that actually appear in the substring)
3. If all these frequencies are the same, they'll form a set with exactly one unique value

The beauty of this approach is that we can check any substring in O(10) = O(1) time (since we only have 10 possible digits), rather than O(length of substring).

Since the problem asks for unique substrings, not just the count of valid positions, we store the actual substring content in a set to automatically handle duplicates. For instance, if "11" appears multiple times in different positions, we only count it once.

Solution Approach

The implementation follows a prefix sum pattern combined with substring enumeration:

1. Building the Prefix Sum Array:

presum = [[0] * 10 for _ in range(n + 1)]

We create a 2D array where presum[i][j] stores the count of digit j in the substring s[0:i]. The array has dimensions (n+1) × 10 to handle all positions and all possible digits (0-9).

2. Populating Prefix Sums:

for i, c in enumerate(s):
    presum[i + 1][int(c)] += 1
    for j in range(10):
        presum[i + 1][j] += presum[i][j]

For each character in the string:

• Increment the count for the current digit at position i+1
• Copy all previous counts from position i to position i+1

This ensures presum[i+1] contains cumulative counts up to and including position i.

3. Validation Function:

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

For substring s[i:j+1]:

• Calculate the frequency of each digit using the difference presum[j+1][k] - presum[i][k]
• Add non-zero frequencies to a set v
• If the set ever contains more than one value, different digits have different frequencies, so return False
• If we finish checking all digits with at most one unique frequency value, return True

4. Finding All Valid Unique Substrings:

vis = set(s[i : j + 1] for i in range(n) for j in range(i, n) if check(i, j))

Using a set comprehension:

• Enumerate all possible substrings with starting index i and ending index j
• Include only those that pass the check function
• The set automatically handles duplicate substrings

5. Return Result:

return len(vis)

The size of the set gives us the count of unique valid substrings.

Time Complexity: O(n² × 10) = O(n²) where n is the length of the string. We check all O(n²) substrings, and each check takes O(10) = O(1) time.

Space Complexity: O(n × 10 + n²) = O(n²) for the prefix sum array and potentially storing all substrings in the set.

Example Walkthrough

Let's walk through the solution with the string s = "1123".

Step 1: Build the prefix sum array

We create a presum array of size (5 × 10) since n = 4:

Initial state: all zeros

Position:  0    1    2    3    4
String:         '1'  '1'  '2'  '3'

Building prefix sums:

• Position 0: All counts are 0 (base case)
• Position 1 (after '1'): digit 1 count = 1
• Position 2 (after '11'): digit 1 count = 2
• Position 3 (after '112'): digit 1 count = 2, digit 2 count = 1
• Position 4 (after '1123'): digit 1 count = 2, digit 2 count = 1, digit 3 count = 1

The presum array (showing only digits 0-3 for brevity):

       digit: 0  1  2  3
position 0:  [0, 0, 0, 0]
position 1:  [0, 1, 0, 0]
position 2:  [0, 2, 0, 0]
position 3:  [0, 2, 1, 0]
position 4:  [0, 2, 1, 1]

Step 2: Check all possible substrings

Now we enumerate all substrings and check if they're valid:

1. Substring "1" (i=0, j=0):

   • Frequency of digit 1: presum[1][1] - presum[0][1] = 1 - 0 = 1
   • Non-zero frequencies: {1}
   • Valid ✓ (only one unique frequency)

2. Substring "11" (i=0, j=1):

   • Frequency of digit 1: presum[2][1] - presum[0][1] = 2 - 0 = 2
   • Non-zero frequencies: {2}
   • Valid ✓

3. Substring "112" (i=0, j=2):

   • Frequency of digit 1: presum[3][1] - presum[0][1] = 2 - 0 = 2
   • Frequency of digit 2: presum[3][2] - presum[0][2] = 1 - 0 = 1
   • Non-zero frequencies: {2, 1}
   • Invalid ✗ (two different frequencies)

4. Substring "1123" (i=0, j=3):

   • Frequency of digit 1: 2 - 0 = 2
   • Frequency of digit 2: 1 - 0 = 1
   • Frequency of digit 3: 1 - 0 = 1
   • Non-zero frequencies: {2, 1}
   • Invalid ✗

5. Substring "1" (i=1, j=1):

   • Frequency of digit 1: presum[2][1] - presum[1][1] = 2 - 1 = 1
   • Non-zero frequencies: {1}
   • Valid ✓ (but duplicate of substring from position 0)

6. Substring "12" (i=1, j=2):

   • Frequency of digit 1: 2 - 1 = 1
   • Frequency of digit 2: 1 - 0 = 1
   • Non-zero frequencies: {1}
   • Valid ✓ (all digits appear once)

7. Substring "123" (i=1, j=3):

   • Frequency of digit 1: 2 - 1 = 1
   • Frequency of digit 2: 1 - 0 = 1
   • Frequency of digit 3: 1 - 0 = 1
   • Non-zero frequencies: {1}
   • Valid ✓ (all digits appear once)

8. Substring "2" (i=2, j=2):

   • Frequency of digit 2: presum[3][2] - presum[2][2] = 1 - 0 = 1
   • Non-zero frequencies: {1}
   • Valid ✓

9. Substring "23" (i=2, j=3):

   • Frequency of digit 2: 1 - 0 = 1
   • Frequency of digit 3: 1 - 0 = 1
   • Non-zero frequencies: {1}
   • Valid ✓

10. Substring "3" (i=3, j=3):

    • Frequency of digit 3: presum[4][3] - presum[3][3] = 1 - 0 = 1
    • Non-zero frequencies: {1}
    • Valid ✓

Step 3: Collect unique valid substrings

Valid substrings found: {"1", "11", "1", "12", "123", "2", "23", "3"}

After removing duplicates (the second "1"): {"1", "11", "12", "123", "2", "23", "3"}

Final Answer: 7 unique valid substrings

Solution Implementation

Time and Space Complexity

Time Complexity: O(n³)

The time complexity breaks down as follows:

• Building the prefix sum array takes O(n × 10) = O(n) time, where we iterate through each character and update 10 digit counters.
• The main nested loops iterate through all possible substrings: O(n²) pairs of (i, j) where i ranges from 0 to n-1 and j ranges from i to n-1.
• For each substring pair (i, j), the check function is called, which iterates through 10 digits to verify if all non-zero digit frequencies are equal. This takes O(10) = O(1) time.
• For each valid substring that passes the check, we create the substring s[i:j+1] which takes O(j - i + 1) time in the worst case, which can be O(n).
• Therefore, the overall time complexity is O(n²) × O(n) = O(n³).

Space Complexity: O(n² + n)

The space complexity consists of:

• The prefix sum array presum uses O((n + 1) × 10) = O(n) space.
• The set vis stores unique substrings. In the worst case where all substrings have equal digit frequency, there are O(n²) possible substrings, and each substring can take up to O(n) space.
• However, since we're storing unique substrings in a set and the total number of unique substrings is bounded by O(n²), the space for vis is O(n²) in total (considering amortized storage).
• Therefore, the overall space complexity is O(n² + n) = O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Substring Frequency Calculation

A common mistake is recalculating digit frequencies from scratch for each substring instead of using prefix sums:

Incorrect/Inefficient Approach:

def check_substring(s, start, end):
    freq = {}
    # Recalculating frequencies for every substring - O(n) per check!
    for i in range(start, end + 1):
        digit = s[i]
        freq[digit] = freq.get(digit, 0) + 1
  
    frequencies = set(freq.values())
    return len(frequencies) <= 1

Why it's problematic: This approach has O(n³) time complexity since we iterate through each substring to count frequencies, making it inefficient for large inputs.

Solution: Use prefix sums to calculate any substring's digit frequencies in O(1) time after O(n) preprocessing.

2. Forgetting to Handle Single Character Substrings

Some implementations might incorrectly assume that single characters don't count as valid substrings:

Incorrect Logic:

# Wrong: skipping single characters
for start in range(n):
    for end in range(start + 1, n):  # Missing single character case!
        if has_equal_frequency(start, end):
            unique_substrings.add(s[start:end + 1])

Solution: Ensure the inner loop starts from start not start + 1:

for start in range(n):
    for end in range(start, n):  # Includes single characters
        if has_equal_frequency(start, end):
            unique_substrings.add(s[start:end + 1])

3. Not Deduplicating Substrings Properly

Using a list instead of a set to store valid substrings leads to counting duplicates:

Incorrect:

valid_substrings = []  # List allows duplicates
for start in range(n):
    for end in range(start, n):
        if has_equal_frequency(start, end):
            valid_substrings.append(s[start:end + 1])
return len(valid_substrings)  # May count "111" multiple times

Solution: Use a set to automatically handle deduplication:

unique_substrings = set()  # Set prevents duplicates

4. Off-by-One Errors in Prefix Sum Calculation

A subtle but critical error is misaligning indices when building or using the prefix sum array:

Incorrect:

# Wrong: Using wrong indices
count = prefix_sum[end][digit] - prefix_sum[start - 1][digit]  # Dangerous if start = 0

Correct:

# Correct: prefix_sum[i] contains counts for s[0:i]
count = prefix_sum[end + 1][digit] - prefix_sum[start][digit]

5. Early Termination Logic Error

Incorrectly implementing the early termination in the frequency check:

Incorrect:

def has_equal_frequency(start, end):
    frequency_set = set()
    for digit in range(10):
        count = prefix_sum[end + 1][digit] - prefix_sum[start][digit]
        if count > 0:
            frequency_set.add(count)
    # Wrong: checking after the loop misses optimization opportunity
    return len(frequency_set) <= 1

Better:

def has_equal_frequency(start, end):
    frequency_set = set()
    for digit in range(10):
        count = prefix_sum[end + 1][digit] - prefix_sum[start][digit]
        if count > 0:
            frequency_set.add(count)
            # Early termination when we know it's invalid
            if len(frequency_set) > 1:
                return False
    return True

This early termination can significantly improve performance, especially for longer strings where invalid substrings are detected early.