Minimum Substring Partition of Equal Character Frequency - Solution & Explanation
Problem Statement
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. The unbalanced substrings are bolded.
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.
Example 1:
Input: s = "fabccddg"
Output: 3
Explanation:
We can partition the string s into 3 substrings in one of the following ways: ("fab, "ccdd", "g"), or ("fabc", "cd", "dg").
Example 2:
Input: s = "abababaccddb"
Output: 2
Explanation:
We can partition the string s into 2 substrings like so: ("abab", "abaccddb").
Constraints:
1 <= s.length <= 1000sconsists only of English lowercase letters.
Approach Overview
Problem Overview: You are given a string s. Split it into the minimum number of substrings such that in every substring each character appears the same number of times. The task is to find the smallest number of partitions that satisfy this equal frequency rule.
Approach 1: Greedy Character Count Verification with DP (Time: O(n^2 * 26), Space: O(n))
This approach builds the answer using dynamic programming. Let dp[i] represent the minimum partitions needed for the prefix ending at index i. For each starting index i, expand the substring to the right and maintain a frequency array for the 26 lowercase letters. At every step compute the number of distinct characters and the maximum frequency. A substring is valid when maxFreq * distinct == length, which guarantees every character appears the same number of times.
Whenever a valid substring s[i..j] appears, update dp[j + 1] = min(dp[j + 1], dp[i] + 1). The algorithm checks all substrings but validates them in constant time using the maintained counts. Character frequency tracking relies on simple counting techniques similar to problems under hash tables and string processing.
This method is straightforward and reliable in interviews because it clearly separates the validation logic (equal character frequency) from the partition optimization (DP).
Approach 2: Sliding Window with Frequent Character Check (Time: O(n^2), Space: O(n))
This variation still uses DP but improves substring validation by maintaining a sliding frequency window as the right pointer moves. For each starting index, extend the window one character at a time and update the frequency counter. Track the maximum character frequency and the number of distinct characters in the window.
The key observation is the same: a substring is balanced if the window length equals maxFreq * distinct. Because counts are updated incrementally, the algorithm avoids recomputing frequencies from scratch for every substring. Once a valid window is detected, update the DP state representing the minimum number of partitions.
This approach is easier to reason about during coding interviews because it follows the familiar expand-window pattern used in many substring problems while still leveraging dynamic programming to minimize partitions.
Recommended for interviews: The greedy frequency verification with DP is the expected solution. It demonstrates understanding of substring validation, frequency counting, and optimal partitioning using dynamic programming. The sliding window variant expresses the same idea more incrementally, but both ultimately achieve the same O(n^2) complexity.
Approach 1: First Approach: Greedy Character Count Verification
This approach involves keeping a count of character frequencies while iterating over the string. When you stumble upon a substring where each character count is balanced, you separate that substring and start a new one.
Using a greedy strategy, iterate through the string, while maintaining a count of character frequencies in the current substring. When the frequencies balance out, make a partition and reset your counts.
In this solution, we use an integer array count to store the frequency of each character. As we iterate over the string, we increase the frequency count and check whenever we encounter the first character of a set. This increment to partitions helps us count the minimum partitions required when frequencies balance out.
Complexity
Time Complexity: O(n), where n is the length of the string, as we traverse it once.
Space Complexity: O(1), considering the fixed size of the alphabet (26 characters).
Approach 2: Second Approach: Sliding Window with Frequent Character Check
This approach uses the sliding window technique combined with frequency validation. As you process the string, maintain a window of character frequencies, and adjust it by checking the balanced condition, which is reset when identified.
With the sliding window method, you use two pointers to expand and contract your window over the string. By monitoring character frequencies within the range, you ensure balanced substrings efficiently.
This C solution implements a helper function to determine if the characters are balanced (all have the same frequency). As the window slides, a check is made, and the counter resets whenever a balanced sequence is found to calculate partitions.
Complexity
Time Complexity: O(26*n), where n is the length of the string, deriving from the nested loop.
Space Complexity: O(1)
Approach 3: Memoized Search + Hash Table
We design a function dfs(i), which represents the minimum number of substrings starting from s[i]. The answer is dfs(0).
The calculation process of the function dfs(i) is as follows:
If i geq n, it means all characters have been processed, so return 0.
Otherwise, we maintain a hash table cnt to represent the frequency of each character in the current substring. Additionally, we maintain a hash table freq to represent the frequency of each character's occurrence count.
Then we enumerate j from i to n-1, representing the end position of the current substring. For each j, we update cnt and freq, then check if the size of freq is 1. If it is, we can split from j+1, and the answer is 1 + dfs(j+1). We take the minimum answer among all j as the return value of the function.
To avoid repeated calculations, we use memoized search.
The time complexity is O(n^2), and the space complexity is O(n times |\Sigma|). Here, n is the length of the string s, and |\Sigma| represents the size of the character set, which is 26 in this problem.
Code
Python
Java
C++
Go
TypeScript
Approach 4: Memoized Search (Optimization)
We can optimize Solution 1 by not maintaining the freq hash table. Instead, we only need to maintain a hash table cnt, which represents the frequency of each character in the current substring. Additionally, we maintain two variables k and m to represent the number of distinct characters in the current substring and the maximum frequency of any character, respectively. For a substring s[i..j], if j-i+1 = m times k, then this substring is a balanced substring.
The time complexity is O(n^2), and the space complexity is O(n times |\Sigma|). Here, n is the length of the string s, and |\Sigma| represents the size of the character set, which is 26 in this problem.
Code
Python
Java
C++
Go
TypeScript
Approach 5: Dynamic Programming
We can convert the memoized search into dynamic programming. Define the state f[i] as the minimum number of substrings required to partition the first i characters. Initially, f[0] = 0, and the rest f[i] = +infty or f[i] = n.
Next, we enumerate i from 0 to n-1. For each i, we maintain a hash table cnt to represent the frequency of each character in the current substring. Additionally, we maintain two variables k and m to represent the number of distinct characters in the current substring and the maximum frequency of any character, respectively. For a substring s[j..i], if i-j+1 = m times k, then this substring is a balanced substring. At this point, we can partition from j, so f[i+1] = min(f[i+1], f[j] + 1).
The final answer is f[n].
The time complexity is O(n^2), and the space complexity is O(n + |\Sigma|). Here, n is the length of the string s, and |\Sigma| represents the size of the character set, which is 26 in this problem.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| First Approach: Greedy Character Count Verification | Time Complexity: O(n), where n is the length of the string, as we traverse it once. |
| Second Approach: Sliding Window with Frequent Character Check | Time Complexity: O(26*n), where n is the length of the string, deriving from the nested loop. |
| Memoized Search + Hash Table | — |
| Memoized Search (Optimization) | — |
| Dynamic Programming | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy Character Count Verification with DP | O(n^2 * 26) | O(n) | General solution. Clear DP formulation and easy substring validity check using frequency counts. |
| Sliding Window with Frequent Character Check | O(n^2) | O(n) | When implementing incremental frequency updates while expanding substrings. |
Video Solution
3144. Minimum Substring Partition of Equal Character Frequency | DP | Memoization • Aryan Mittal • 3,834 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Minimum Substring Partition of Equal Character Frequency easy or hard?
Minimum Substring Partition of Equal Character Frequency Python/Java solution
How to solve Minimum Substring Partition of Equal Character Frequency in O(n)?
What is the best approach for Minimum Substring Partition of Equal Character Frequency?
Is Minimum Substring Partition of Equal Character Frequency asked at Google/Amazon/Meta?
What data structure is used in Minimum Substring Partition of Equal Character Frequency?
What is the time complexity of Minimum Substring Partition of Equal Character Frequency?
Ready to solve this problem?
Practice Minimum Substring Partition of Equal Character Frequency with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor