Number of Equal Count Substrings - Practice Coding Problems

Number of Equal Count Substrings - Problem

You are given a 0-indexed string s consisting of only lowercase English letters, and an integer count.

A substring of s is said to be an equal count substring if, for each unique letter in the substring, it appears exactly count times in the substring.

Return the number of equal count substrings in s.

A substring is a contiguous non-empty sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: s = "aaabbbccc", count = 3

› Output: 3

💡 Note: The equal count substrings are "aaa", "bbb", and "ccc". Each contains one unique character that appears exactly 3 times.

Example 2 — Mixed Characters

$ Input: s = "abababab", count = 2

› Output: 2

💡 Note: The equal count substrings are "abab" (positions 0-3) and "abab" (positions 2-5). Each contains 'a' twice and 'b' twice.

Example 3 — No Valid Substrings

$ Input: s = "abcdef", count = 2

› Output: 0

💡 Note: No substring has any character appearing exactly 2 times, so there are 0 equal count substrings.

Constraints

1 ≤ s.length ≤ 1000
1 ≤ count ≤ s.length
s consists of only lowercase English letters

Visualization

Tap to expand

Understanding the Visualization

Input

String s and target count value

Process

Check each substring's character frequencies

Output

Count of valid equal count substrings

Key Takeaway

🎯 Key Insight: A substring is valid if every unique character in it appears exactly count times

Asked in

G Google 25 M Microsoft 20 a Amazon 15 f Facebook 12

The key insight is to check all possible substrings and verify that each unique character appears exactly count times. The sliding window approach optimizes the frequency tracking. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible substrings and count frequencies for each
Sliding Window	O(n²)	O(1)	Use sliding window with frequency tracking for efficiency

Brute Force — Algorithm Steps

Step 1: Generate all possible substrings
Step 2: For each substring, count character frequencies
Step 3: Check if all frequencies equal count

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible substrings

Count Frequencies

Count each character in substring

Validate

Check if all frequencies equal count

Code -

solution.c — C

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

int solution(char* s, int count) {
    int n = strlen(s);
    int result = 0;
    
    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int freq[26] = {0};
            int uniqueChars = 0;
            
            // Count frequencies for substring s[i..j]
            for (int k = i; k <= j; k++) {
                if (freq[s[k] - 'a'] == 0) {
                    uniqueChars++;
                }
                freq[s[k] - 'a']++;
            }
            
            // Check if all frequencies equal count
            int valid = 1;
            for (int k = 0; k < 26; k++) {
                if (freq[k] > 0 && freq[k] != count) {
                    valid = 0;
                    break;
                }
            }
            
            if (valid) {
                result++;
            }
        }
    }
    
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: two for substring bounds and one to count frequencies

⚠ Quadratic Growth

Space Complexity

O(1)

Only using a fixed-size frequency array for 26 letters

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 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