Minimum Substring Partition of Equal Character Frequency - Video Solutions

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.