Minimum Substring Partition of Equal Character Frequency solution and explanation
9 more videos on this problem
3144. Minimum Substring Partition of Equal Character Frequency | DP | MemoizationAryan Mittal · 27:29 · 3K views
3144. Minimum Substring Partition of Equal Character Freqcy | HARDER VERSION | Leetcode Biweekly 130codingMohan · 41:18 · 842 views
3144. Minimum Substring Partition of Equal Character Frequency (Leetcode Medium)Programming Live with Larry · 15:15 · 566 views
Minimum Substring Partition of Equal Character Frequency | DP |memoization | Biweekly 130 | C++Priyanshi Porwal · 21:59 · 495 views
100289 Minimum Substring Partition of Equal Character Frequency | Detailed Explanation With Code.Pretest Passed · 11:30 · 321 views
3144. Minimum Substring Partition of Equal Character Frequency | Recursion | DP | MemoizationLeet's Code · 7:09 · 288 views
Minimum Substring Partition of Equal Character Frequency (LeetCode Q3144kode · 22:33 · 66 views
Leetcode Biweekly Contest 130 C Minimum Substring Partition Of Equal Character Frequency Solutioncode conqueror · 0:07 · 48 views
Solving LC Biweekly Contest 130. | LC 3144. Minimum Substring Partition of Equal Character FrequencyLet's Solve · 27:55 · 47 views
3144. Minimum Substring Partition of Equal Character Frequency 分割字符频率相等的最少子字符串 LeetCode 力扣题解程序员写代码 · 9:25 · 29 views
The 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. 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.
def min_partitions(s):
count = [0] * 26
unique = 0
partitions = 0
for c in s:
idx = ord(c) - ord('a')
count[idx] += 1
if count[idx] == 1:
unique += 1
if unique == len(set(count)):
partitions += 1
return partitions
print(min_partitions("fabccddg")) # Output: 3public class Main {
public static int minPartitions(String s) {
int[] count = new int[26];
int unique = 0, partitions = 0;
for (char c : s.toCharArray()) {
count[c - 'a']++;
if (count[c - 'a'] == 1) unique++;
if (unique == 1) partitions++;
}
return partitions;
}
public static void main(String[] args) {
String s = "fabccddg";
System.out.println(minPartitions(s)); // Output: 3
}
}#include <iostream>
#include <vector>
int minPartitions(const std::string& s) {
std::vector<int> count(26, 0);
int unique = 0, partitions = 0;
for (const char& c : s) {
count[c - 'a']++;
if (count[c - 'a'] == 1) unique++;
if (unique == 1) partitions++;
}
return partitions;
}
int main() {
std::string s = "fabccddg";
std::cout << minPartitions(s) << std::endl; // Output: 3
return 0;
}function minPartitions(s) {
const count = Array(26).fill(0);
let unique = 0, partitions = 0;
for (let i = 0; i < s.length; i++) {
const index = s.charCodeAt(i) - 'a'.charCodeAt(0);
count[index]++;
if (count[index] === 1) unique++;
if (unique === new Set(count.filter(x => x > 0)).size) partitions++;
}
return partitions;
}
console.log(minPartitions('fabccddg')); // Output: 3#include <stdio.h>
#include <string.h>
int minPartitions(char* s) {
int count[26] = {0};
int unique = 0, partitions = 0;
for (int i = 0; s[i] != '\0'; i++) {
count[s[i] - 'a']++;
if (count[s[i] - 'a'] == 1) unique++;
if (unique == 1) partitions++;
}
return partitions;
}
int main() {
char s[] = "fabccddg";
printf("%d\n", minPartitions(s)); // Output: 3
return 0;
}using System;
class Program
{
static int MinPartitions(string s)
{
int[] count = new int[26];
int unique = 0, partitions = 0;
foreach (char c in s)
{
count[c - 'a']++;
if (count[c - 'a'] == 1) unique++;
if (unique == 1) partitions++;
}
return partitions;
}
static void Main()
{
var s = "fabccddg";
Console.WriteLine(MinPartitions(s)); // Output: 3
}
}The Python solution keeps track of character frequencies using a list and updates the count for each character encountered. It checks if there is a unique count ready for partitioning a balanced set.
Time Complexity: O(n)
Space Complexity: O(1)
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.
def is_balanced(count):
freqs = [c for c in count if c > 0]
return len(set(freqs)) == 1
def min_substrings(s):
count = [0] * 26
partitions = 0
for c in s:
idx = ord(c) - ord('a')
count[idx] += 1
if is_balanced(count):
partitions += 1
count = [0] * 26 # Reset
return partitions
print(min_substrings("fabccddg")) # Output: 3public class Main {
private static boolean isBalanced(int[] count) {
int freq = -1;
for (int i = 0; i < count.length; i++) {
if (count[i] != 0) {
if (freq == -1) freq = count[i];
else if (count[i] != freq) return false;
}
}
return true;
}
public static int minSubstrings(String s) {
int[] count = new int[26];
int partitions = 0;
for (char c : s.toCharArray()) {
count[c - 'a']++;
if (isBalanced(count)) {
partitions++;
Arrays.fill(count, 0); // Reset count
}
}
return partitions;
}
public static void main(String[] args) {
String s = "fabccddg";
System.out.println(minSubstrings(s)); // Output: 3
}
}#include <iostream>
#include <vector>
bool isBalanced(const std::vector<int>& count) {
int freq = -1;
for (size_t i = 0; i < count.size(); ++i) {
if (count[i] != 0) {
if (freq == -1) freq = count[i];
else if (count[i] != freq) return false;
}
}
return true;
}
int minSubstrings(std::string s) {
std::vector<int> count(26, 0);
int partitions = 0;
for (char c : s) {
count[c - 'a']++;
if (isBalanced(count)) {
partitions++;
count.assign(26, 0); // Reset count
}
}
return partitions;
}
int main() {
std::string s = "fabccddg";
std::cout << minSubstrings(s) << std::endl; // Output: 3
return 0;
}function isBalanced(count) {
const freqs = count.filter(c => c > 0);
return new Set(freqs).size === 1;
}
function minSubstrings(s) {
const count = Array(26).fill(0);
let partitions = 0;
for (let i = 0; i < s.length; i++) {
const index = s.charCodeAt(i) - 'a'.charCodeAt(0);
count[index]++;
if (isBalanced(count)) {
partitions++;
count.fill(0); // Reset count
}
}
return partitions;
}
console.log(minSubstrings('fabccddg')); // Output: 3#include <stdio.h>
#include <stdbool.h>
bool isBalanced(int* count, int unique) {
int freq = -1;
for (int i = 0; i < 26; i++) {
if (count[i] != 0) {
if (freq == -1) freq = count[i];
else if (count[i] != freq) return false;
}
}
return true;
}
int minSubstrings(char* s) {
int count[26] = {0}, unique = 0, partitions = 0;
for (int end = 0; s[end] != '\0'; end++) {
count[s[end] - 'a']++;
if (isBalanced(count, unique)) {
partitions++;
for (int i = 0; i < 26; i++) count[i] = 0; // Reset count
}
}
return partitions;
}
int main() {
char s[] = "fabccddg";
printf("%d\n", minSubstrings(s)); // Output: 3
return 0;
}using System;
using System.Linq;
class Program
{
static bool IsBalanced(int[] count)
{
var freqs = count.Where(c => c > 0);
return freqs.Distinct().Count() == 1;
}
static int MinSubstrings(string s)
{
int[] count = new int[26];
int partitions = 0;
foreach (char c in s)
{
count[c - 'a']++;
if (IsBalanced(count))
{
partitions++;
Array.Clear(count, 0, count.Length); // Reset count
}
}
return partitions;
}
static void Main()
{
var s = "fabccddg";
Console.WriteLine(MinSubstrings(s)); // Output: 3
}
}The Python solution follows checking for balance after updating character frequency counts. If balanced, it increments partition counts and resets for the next substrings.
Time Complexity: O(26*n)
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.
function minimumSubstringsInPartition(s: string): number {
const n = s.length;
const f: number[] = Array(n).fill(-1);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i] !== -1) {
return f[i];
}
const cnt: Map<number, number> = new Map();
const freq: Map<number, number> = new Map();
f[i] = n - i;
for (let j = i; j < n; ++j) {
const k = s.charCodeAt(j) - 97;
if (freq.has(cnt.get(k)!)) {
freq.set(cnt.get(k)!, freq.get(cnt.get(k)!)! - 1);
if (freq.get(cnt.get(k)!) === 0) {
freq.delete(cnt.get(k)!);
}
}
cnt.set(k, (cnt.get(k) || 0) + 1);
freq.set(cnt.get(k)!, (freq.get(cnt.get(k)!) || 0) + 1);
if (freq.size === 1) {
f[i] = Math.min(f[i], 1 + dfs(j + 1));
}
}
return f[i];
};
return dfs(0);
}func minimumSubstringsInPartition(s string) int {
n := len(s)
f := make([]int, n)
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != -1 {
return f[i]
}
cnt := [26]int{}
freq := map[int]int{}
f[i] = n - i
for j := i; j < n; j++ {
k := int(s[j] - 'a')
if cnt[k] > 0 {
freq[cnt[k]]--
if freq[cnt[k]] == 0 {
delete(freq, cnt[k])
}
}
cnt[k]++
freq[cnt[k]]++
if len(freq) == 1 {
f[i] = min(f[i], 1+dfs(j+1))
}
}
return f[i]
}
return dfs(0)
}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.
function minimumSubstringsInPartition(s: string): number {
const n = s.length;
const f: number[] = Array(n).fill(-1);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i] !== -1) {
return f[i];
}
const cnt: number[] = Array(26).fill(0);
f[i] = n - i;
let [k, m] = [0, 0];
for (let j = i; j < n; ++j) {
const x = s.charCodeAt(j) - 97;
k += ++cnt[x] === 1 ? 1 : 0;
m = Math.max(m, cnt[x]);
if (j - i + 1 === k * m) {
f[i] = Math.min(f[i], 1 + dfs(j + 1));
}
}
return f[i];
};
return dfs(0);
}func minimumSubstringsInPartition(s string) int {
n := len(s)
f := make([]int, n)
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != -1 {
return f[i]
}
cnt := [26]int{}
f[i] = n - i
k, m := 0, 0
for j := i; j < n; j++ {
x := int(s[j] - 'a')
cnt[x]++
if cnt[x] == 1 {
k++
}
m = max(m, cnt[x])
if j-i+1 == k*m {
f[i] = min(f[i], 1+dfs(j+1))
}
}
return f[i]
}
return dfs(0)
}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.
function minimumSubstringsInPartition(s: string): number {
const n = s.length;
const f: number[] = Array(n + 1).fill(n);
f[0] = 0;
for (let i = 0; i < n; ++i) {
const cnt: number[] = Array(26).fill(0);
let [k, m] = [0, 0];
for (let j = i; ~j; --j) {
const x = s.charCodeAt(j) - 97;
k += ++cnt[x] === 1 ? 1 : 0;
m = Math.max(m, cnt[x]);
if (i - j + 1 === k * m) {
f[i + 1] = Math.min(f[i + 1], 1 + f[j]);
}
}
}
return f[n];
}func minimumSubstringsInPartition(s string) int {
n := len(s)
f := make([]int, n+1)
for i := range f {
f[i] = n
}
f[0] = 0
for i := 0; i < n; i++ {
cnt := [26]int{}
k, m := 0, 0
for j := i; j >= 0; j-- {
x := int(s[j] - 'a')
cnt[x]++
if cnt[x] == 1 {
k++
}
m = max(m, cnt[x])
if i-j+1 == k*m {
f[i+1] = min(f[i+1], 1+f[j])
}
}
}
return f[n]
}Complexity comparison
| Approach | Complexity |
|---|---|
| First Approach: Greedy Character Count Verification | Time Complexity: O(n) |
| Second Approach: Sliding Window with Frequent Character Check | Time Complexity: O(26*n) |
| Memoized Search + Hash Table | – |
| Memoized Search (Optimization) | – |
| Dynamic Programming | – |
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. |
Frequently asked questions
Is Minimum Substring Partition of Equal Character Frequency easy or hard?
The problem is rated Medium on LeetCode. The challenge comes from recognizing the equal-frequency property and combining substring validation with dynamic programming to minimize partitions.
Minimum Substring Partition of Equal Character Frequency Python/Java solution
Implement a dynamic programming array where dp[i] stores the minimum partitions for the prefix ending at i. For each starting index, maintain a 26-length frequency array while expanding the substring. When the substring satisfies maxFreq * distinct == length, update the DP state. The same logic works in Python, Java, C++, and other languages.
How to solve Minimum Substring Partition of Equal Character Frequency in O(n)?
An O(n) solution is not generally feasible because every potential substring boundary may need to be checked. Most accepted solutions rely on O(n^2) dynamic programming combined with frequency counting. The optimization comes from validating substrings in constant time using maintained counts instead of recomputing them.
What is the best approach for Minimum Substring Partition of Equal Character Frequency?
The most common approach uses dynamic programming with character frequency counting. For every starting index, expand the substring and maintain counts of characters. A substring is valid when the length equals maxFrequency multiplied by the number of distinct characters. This leads to an O(n^2) solution with O(n) DP space.
Is Minimum Substring Partition of Equal Character Frequency asked at Google/Amazon/Meta?
Problems involving substring partitioning, frequency balancing, and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that combine string processing with DP are especially common in mid‑level and senior coding interviews.
What data structure is used in Minimum Substring Partition of Equal Character Frequency?
The solution mainly uses a frequency array or hash table to count characters, along with a dynamic programming array to store the minimum number of partitions. These structures allow constant-time updates while scanning substrings.
What is the time complexity of Minimum Substring Partition of Equal Character Frequency?
The typical solution runs in O(n^2) time. For each starting index you extend the substring while maintaining character frequencies, which takes constant time per extension because the alphabet size is fixed. Space complexity is O(n) for the dynamic programming array.