Unique Substrings With Equal Digit Frequency

Unique Substrings With Equal Digit Frequency - Problem

\ Medium

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.

Examples of valid substrings:

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

Examples of invalid substrings:

In substring "1123", digit 1 appears 2 times while digits 2 and 3 appear 1 time each - this is invalid

Note: The function should return the count of unique substrings that satisfy this condition.

Input & Output

Example 1 — Basic Case

$ Input: s = "1122"

› Output: 5

💡 Note: Valid substrings: "1" (appears twice), "2" (appears twice), "11" (digit 1 appears 2 times), "22" (digit 2 appears 2 times), "1122" (both digits appear 2 times each)

Example 2 — Single Digit

$ Input: s = "111"

› Output: 3

💡 Note: Valid substrings: "1" (appears 3 times as individual substrings), "11" (appears twice), "111" (digit 1 appears 3 times)

Example 3 — Mixed Frequencies

$ Input: s = "1123"

› Output: 6

💡 Note: Valid substrings: "1" (appears twice individually), "2", "3", "11" (digit 1 appears 2 times), "23" (both digits appear 1 time each)

Constraints

1 ≤ s.length ≤ 1000
s consists only of digits (0-9)

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Given string with digits, identify all possible substrings

Frequency Check

For each substring, verify all present digits have same count

Count Unique

Return number of unique valid substrings

Key Takeaway

🎯 Key Insight: Use prefix sums to calculate digit frequencies efficiently, then validate equal frequency constraint

Asked in

G Google 25 a Amazon 18 f Facebook 12

The key insight is to use prefix sums to efficiently calculate digit frequencies for any substring in O(1) time. The optimal approach builds a prefix array storing cumulative counts of each digit, then validates substrings by checking if all present digits have equal frequency. Time: O(n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(n³)	Check every possible substring and count digit frequencies
Prefix Sum Optimization	O(n²)	O(n²)	Use prefix sums to calculate digit frequencies in O(1) time for any substring

Brute Force — Algorithm Steps

Step 1: Generate all possible substrings using nested loops
Step 2: For each substring, count frequency of each digit
Step 3: Check if all present digits have same frequency
Step 4: Add valid substrings to set for uniqueness

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings using nested loops

Count Frequencies

For each substring, count how often each digit appears

Validate Equal Frequency

Check if all present digits have the same frequency

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s) {
    int n = strlen(s);
    char substrings[1000][1000];
    int uniqueCount = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            char substring[1000];
            strncpy(substring, s + i, j - i + 1);
            substring[j - i + 1] = '\0';
            
            // Count frequency of each digit
            int freq[10] = {0};
            for (int k = 0; k <= j - i; k++) {
                freq[substring[k] - '0']++;
            }
            
            // Check if all frequencies are equal
            int firstFreq = -1;
            int valid = 1;
            for (int k = 0; k < 10; k++) {
                if (freq[k] > 0) {
                    if (firstFreq == -1) {
                        firstFreq = freq[k];
                    } else if (freq[k] != firstFreq) {
                        valid = 0;
                        break;
                    }
                }
            }
            
            if (valid) {
                // Check if substring is already counted
                int found = 0;
                for (int k = 0; k < uniqueCount; k++) {
                    if (strcmp(substrings[k], substring) == 0) {
                        found = 1;
                        break;
                    }
                }
                if (!found) {
                    strcpy(substrings[uniqueCount], substring);
                    uniqueCount++;
                }
            }
        }
    }
    
    return uniqueCount;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

O(n²) substrings, each taking O(n) time to process

⚠ Quadratic Growth

Space Complexity

O(n³)

Set can store up to O(n²) substrings, each of length O(n)

⚠ Quadratic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler