Minimum Substring Partition of Equal Character Frequency

Minimum Substring Partition of Equal Character Frequency - Problem

Given a string s, you need to partition it into one or more balanced substrings.

For example, if s == "ababcc" then ("abab", "c", "c"), ("ab", "abc", "c"), and ("ababcc") are all valid partitions, but ("a", "bab", "cc"), ("aba", "bc", "c"), and ("ab", "abcc") are not valid because they contain unbalanced substrings.

Return the minimum number of substrings that you can partition s into.

Note: A balanced string is a string where each character in the string occurs the same number of times.

Input & Output

Example 1 — Basic Case

$ Input: s = "ababcc"

› Output: 3

💡 Note: We can partition into ("abab", "c", "c"). "abab" has a:2, b:2 (balanced), each "c" has c:1 (balanced). Total: 3 partitions.

Example 2 — Single Character

$ Input: s = "aaaa"

› Output: 1

💡 Note: The entire string "aaaa" has a:4, so it's balanced. We need only 1 partition.

Example 3 — All Different Characters

$ Input: s = "abc"

› Output: 3

💡 Note: Each character appears once, so "a", "b", "c" are each balanced. We need 3 partitions.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String "ababcc" needs partitioning

Process

Find cuts where each part has equal character frequencies

Output

Minimum 3 partitions: "abab", "c", "c"

Key Takeaway

🎯 Key Insight: Use dynamic programming to try all possible partition points and find the minimum number of balanced substrings

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is recognizing this as a dynamic programming problem where we need to find optimal partition points. The memoized approach is most reliable, trying all possible cuts and caching results. Best approach uses top-down DP with memoization. Time: O(n³), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Approach	O(n²)	O(1)	Extend each partition until it becomes balanced, then start new partition
Brute Force Recursion	O(2^n)	O(n)	Try all possible partitions recursively and find minimum
Dynamic Programming with Memoization	O(n³)	O(n)	Cache results of subproblems to avoid redundant calculations

Greedy Approach — Algorithm Steps

Start with empty current partition
Add characters one by one
Check if current partition is balanced
If balanced, increment count and start new partition

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Begin new partition

Extend

Add characters until balanced

Cut

Make cut when partition becomes balanced

Code -

solution.c — C

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

int isBalanced(int charCount[26], int uniqueChars) {
    if (uniqueChars == 0) return 0;
    
    int frequency = -1;
    for (int i = 0; i < 26; i++) {
        if (charCount[i] > 0) {
            if (frequency == -1) {
                frequency = charCount[i];
            } else if (charCount[i] != frequency) {
                return 0;
            }
        }
    }
    
    return 1;
}

int solution(char* s) {
    int n = strlen(s);
    int count = 0;
    int i = 0;
    
    while (i < n) {
        int charCount[26] = {0};
        int uniqueChars = 0;
        int j = i;
        
        while (j < n) {
            if (charCount[s[j] - 'a'] == 0) {
                uniqueChars++;
            }
            charCount[s[j] - 'a']++;
            
            if (isBalanced(charCount, uniqueChars)) {
                count++;
                i = j + 1;
                break;
            }
            j++;
        }
        
        if (j == n && !isBalanced(charCount, uniqueChars)) {
            break;
        }
    }
    
    return count;
}

int main() {
    char s[1001];
    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²)

One pass through string, but checking balance takes O(n) time in worst case

⚠ Quadratic Growth

Space Complexity

O(1)

Only uses constant extra space for character frequency counting

✓ Linear Space

23.4K Views

Medium Frequency

~25 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

Greedy Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler