Maximum Number of Occurrences of a Substring

Maximum Number of Occurrences of a Substring - Problem

Given a string s, return the maximum number of occurrences of any substring under the following rules:

The number of unique characters in the substring must be less than or equal to maxLetters.
The substring size must be between minSize and maxSize inclusive.

Input & Output

Example 1 — Basic Case

$ Input: s = "aababcaab", maxLetters = 2, minSize = 3, maxSize = 4

› Output: 2

💡 Note: Substring "aab" appears twice and has 2 unique characters (≤ maxLetters), length 3 (within range). Other valid substrings appear only once.

Example 2 — No Valid Substrings

$ Input: s = "aaaa", maxLetters = 1, minSize = 3, maxSize = 3

› Output: 2

💡 Note: Substring "aaa" appears 2 times (positions 0-2 and 1-3), has 1 unique character (≤ maxLetters), length 3 (within range).

Example 3 — All Different Characters

$ Input: s = "abcde", maxLetters = 2, minSize = 2, maxSize = 3

› Output: 0

💡 Note: No substring can satisfy maxLetters = 2, since even the shortest substrings of length 2 have 2 different characters, but we need exactly 2 different characters maximum. All substrings of length 2 like "ab", "bc" have exactly 2 characters which satisfies the constraint, so answer is 1.

Constraints

1 ≤ s.length ≤ 10⁵
1 ≤ maxLetters ≤ 26
1 ≤ minSize ≤ maxSize ≤ min(26, s.length)

Visualization

Tap to expand

Understanding the Visualization

Input

String s with constraints: maxLetters, minSize, maxSize

Process

Find all valid substrings and count occurrences

Output

Return maximum occurrence count

Key Takeaway

🎯 Key Insight: Focus only on minimum size substrings - they always appear most frequently among valid options

Asked in

F Facebook 12 G Google 8 a Amazon 6

The key insight is that shorter valid substrings always appear at least as frequently as longer ones containing them. Therefore, we only need to check substrings of minSize length. Best approach uses sliding window with hash map for O(n) time complexity with O(n) space.

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Hash Map	O(n × (maxSize - minSize))	O(n)	Use sliding window to generate substrings efficiently and hash map to count
Optimized - Focus on Minimum Size	O(n)	O(n)	Only check substrings of minimum size for maximum frequency
Brute Force - Check All Substrings	O(n³)	O(n²)	Generate all possible substrings and count occurrences of valid ones

Sliding Window with Hash Map — Algorithm Steps

For each length from minSize to maxSize
Use sliding window to traverse string
Maintain character frequency map
Count valid substrings

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Window

Set up first window and count characters

Slide Window

Add new character, remove old character

Validate & Count

Check unique character constraint

Code -

solution.c — C

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

int solution(char* s, int maxLetters, int minSize, int maxSize) {
    int n = strlen(s);
    int maxCount = 0;
    
    // Simple implementation with fixed arrays
    char substrings[1000][100];
    int counts[1000];
    int numSubstrings = 0;
    
    // Try each valid length
    for (int length = minSize; length <= maxSize; length++) {
        // Sliding window approach
        for (int i = 0; i <= n - length; i++) {
            char substring[100];
            strncpy(substring, s + i, length);
            substring[length] = '\0';
            
            // Count unique characters in window
            int charFreq[256] = {0};
            int uniqueCount = 0;
            for (int j = 0; j < length; j++) {
                if (charFreq[(int)substring[j]] == 0) {
                    uniqueCount++;
                }
                charFreq[(int)substring[j]]++;
            }
            
            // Check if valid
            if (uniqueCount <= maxLetters) {
                // Find existing substring
                int found = -1;
                for (int k = 0; k < numSubstrings; k++) {
                    if (strcmp(substrings[k], substring) == 0) {
                        found = k;
                        break;
                    }
                }
                
                if (found >= 0) {
                    counts[found]++;
                } else {
                    strcpy(substrings[numSubstrings], substring);
                    counts[numSubstrings] = 1;
                    numSubstrings++;
                }
            }
        }
    }
    
    // Find maximum count
    for (int i = 0; i < numSubstrings; i++) {
        if (counts[i] > maxCount) {
            maxCount = counts[i];
        }
    }
    
    return maxCount;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n × (maxSize - minSize))

For each valid length, slide window across string once

✓ Linear Growth

Space Complexity

O(n)

Hash maps for character frequencies and substring counts

⚡ Linearithmic Space

23.0K 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

Sliding Window with Hash Map — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler