# Minimum Substring Partition of Equal Character Frequency
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-substring-partition-of-equal-character-frequency)
Canonical: https://scaleengineer.com/dsa/problems/minimum-substring-partition-of-equal-character-frequency
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## 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 <= 1000`
* `s` consists only of English lowercase letters.

# Approaches
## Brute-Force Dynamic Programming
This approach uses a straightforward dynamic programming solution. We define `dp[i]` as the minimum number of balanced substrings needed to partition the prefix of the string of length `i`. To compute `dp[i]`, we try every possible last substring `s[j...i-1]`. If this substring is balanced, we can form a partition by taking the optimal solution for the prefix `s[0...j-1]` (which is `dp[j]`) and adding this one last substring. We check every possible split point `j` and take the one that results in the minimum partitions.
**Time:** O(n^3) - There are two nested loops for `i` and `j`, giving `O(n^2)` states. For each state, the `isBalanced` check iterates over the substring of length `i-j`, which can be up to `O(n)`. This results in a total time complexity of `O(n^2 * n) = O(n^3)`. · **Space:** O(n) - We use an `O(n)` array for the DP table. The frequency map inside the helper function takes `O(1)` space. In some languages, creating a substring might take `O(n)` space, but the dominant factor is the DP array.
**Pros:** The logic is a direct translation of the problem's recurrence relation, making it relatively easy to understand.; It correctly solves the problem for small input sizes.
**Cons:** The `O(n^3)` time complexity is inefficient and will likely result in a 'Time Limit Exceeded' error for larger inputs (e.g., `n=1000`).; It performs a lot of redundant work by repeatedly calculating character frequencies for overlapping substrings.
### Explanation
We build a solution from the ground up using dynamic programming. Let `dp[i]` be the minimum number of partitions for the prefix `s[0...i-1]`. Our goal is to find `dp[n]`. The base case is `dp[0] = 0`, as an empty string requires no partitions.

To compute `dp[i]`, we consider all possible substrings `s[j...i-1]` that can end at index `i-1`. For each `j` from `0` to `i-1`, we check if the substring `s[j...i-1]` is balanced. This check is done using a helper function that counts character frequencies within the substring and ensures all non-zero counts are equal.

If `s[j...i-1]` is indeed balanced, we have found a valid partition. The total number of partitions for `s[0...i-1]` would be `1` (for `s[j...i-1]`) plus the minimum partitions for the preceding part of the string, `s[0...j-1]`, which is already computed and stored in `dp[j]`. We update `dp[i]` by taking the minimum over all valid `j`'s: `dp[i] = min(dp[i], dp[j] + 1)`.

This process is repeated for all `i` from `1` to `n`. The main drawback is that for each pair of `(i, j)`, we create and analyze the substring from scratch, leading to a cubic time complexity.

```java
class Solution {
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // Worst case: partition into i single characters
        }
        dp[0] = 0;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                // Substring from index j to i-1
                if (isBalanced(s, j, i)) {
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }

    private boolean isBalanced(String s, int start, int end) {
        int[] counts = new int[26];
        for (int i = start; i < end; i++) {
            counts[s.charAt(i) - 'a']++;
        }

        int freq = -1;
        for (int count : counts) {
            if (count > 0) {
                if (freq == -1) {
                    freq = count;
                } else if (freq != count) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 1`, where `n` is the length of the string `s`.
- `dp[i]` will store the minimum number of balanced partitions for the prefix `s[0...i-1]`.
- Initialize `dp[0] = 0` and `dp[i]` to a large value (e.g., `i`) for `i > 0`.
- Iterate `i` from `1` to `n`:
  - For each `i`, iterate `j` from `0` to `i-1`.
  - In the inner loop, extract the substring `sub = s.substring(j, i)`.
  - Check if `sub` is a balanced string by creating a frequency map and verifying that all characters present have the same frequency.
  - If `sub` is balanced, it represents a valid final partition for the prefix of length `i`. We can then update `dp[i]` with the formula: `dp[i] = min(dp[i], dp[j] + 1)`.
- After the loops complete, `dp[n]` will hold the minimum number of partitions for the entire string `s`.

## Optimized Dynamic Programming
This approach significantly optimizes the brute-force DP solution. The DP state and recurrence relation remain the same, but we change how we check for balanced substrings. Instead of re-calculating frequencies for every substring `s[j...i-1]`, we fix the endpoint `i` and iterate the start point `j` backwards from `i-1` to `0`. As we do this, we can build the frequency map of the substring `s[j...i-1]` incrementally. This avoids the expensive substring creation and re-scanning, reducing the work inside the inner loop to constant time and bringing the overall time complexity down to `O(n^2)`.
**Time:** O(n^2) - The outer loop for `i` runs `n` times. The inner loop for `j` also runs up to `n` times. Inside the inner loop, all operations (updating the frequency map and checking if it's balanced) take constant time, `O(26)` or `O(1)`. This leads to a total time complexity of `O(n * n * 1) = O(n^2)`. · **Space:** O(n) - The DP array `dp` requires `O(n)` space. The frequency map `counts` used inside the loop is re-initialized for each `i` and takes constant `O(1)` space (size 26).
**Pros:** The `O(n^2)` time complexity is efficient enough to pass for `n <= 1000`.; It's a standard and powerful optimization technique for DP problems on substrings.; Space complexity remains optimal at `O(n)`.
**Cons:** Slightly more complex to implement compared to the brute-force method due to the incremental state management in the inner loop.
### Explanation
The core idea is to eliminate the redundant work of the `O(n^3)` approach. We still use a DP array `dp` where `dp[i]` is the minimum partitions for `s[0...i-1]`.

The optimization comes from how we structure the inner loops. For each `i` from `1` to `n`, we want to find the best split point `j`. Instead of iterating `j` forward and re-evaluating the substring `s[j...i-1]` each time, we iterate `j` backwards from `i-1` down to `0`.

For a fixed `i`, we initialize a frequency map. Then, as `j` goes from `i-1` down to `0`, we are considering the substrings `s[i-1...i-1]`, `s[i-2...i-1]`, `s[i-3...i-1]`, and so on. We can maintain the frequency map for this growing substring by simply adding the new character `s.charAt(j)` at each step. After each addition, we perform a quick `O(1)` check on the frequency map to see if it represents a balanced string. If it does, we apply the DP transition `dp[i] = Math.min(dp[i], dp[j] + 1)`.

This way, the check for a balanced substring of length `k` is done in `O(1)` time instead of `O(k)`, making the overall algorithm much faster and suitable for the given constraints.

```java
class Solution {
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        int[] dp = new int[n + 1];
        
        // dp[i] stores the minimum partitions for prefix s[0...i-1]
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[i] = i; // Initialize with worst case (i partitions of length 1)
        }

        for (int i = 1; i <= n; i++) {
            int[] counts = new int[26];
            // Iterate backwards from i-1 to check for balanced substrings ending at i-1.
            // j is the start index of the potential last substring.
            for (int j = i - 1; j >= 0; j--) {
                // Add current character to the frequency map for substring s[j...i-1]
                counts[s.charAt(j) - 'a']++;
                
                // Check if this substring is balanced
                if (isBalanced(counts)) {
                    // If s[j...i-1] is balanced, we can make a partition.
                    // The number of partitions would be 1 (for this substring) +
                    // the minimum partitions for the prefix s[0...j-1], which is dp[j].
                    dp[i] = Math.min(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n];
    }

    private boolean isBalanced(int[] counts) {
        int freq = 0; // Stores the frequency of the first character group found
        for (int count : counts) {
            if (count > 0) {
                if (freq == 0) {
                    freq = count;
                } else if (freq != count) {
                    return false;
                }
            }
        }
        return true;
    }
}
```
### Algorithm
- Create a DP array `dp` of size `n + 1` and initialize it as in the previous approach (`dp[0] = 0`, `dp[i] = i`).
- Iterate `i` from `1` to `n` to compute `dp[i]`.
- For each `i`, start an inner loop with `j` iterating backwards from `i-1` down to `0`.
- Maintain a single frequency map (`counts` array) for the current outer loop `i`.
- In the inner loop (for `j`), you are considering substrings `s[j...i-1]`. As `j` decreases, the substring extends to the left.
- Update the `counts` array by incrementing the count for `s.charAt(j)`.
- After updating, check if the `counts` array represents a balanced string. This check takes constant time (`O(26)`).
- If it is balanced, update `dp[i] = min(dp[i], dp[j] + 1)`.
- Return `dp[n]` as the final result.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  char[] s;
private
  Integer[] f;
public
  int minimumSubstringsInPartition(String s) {
    n = s.length();
    f = new Integer[n];
    this.s = s.toCharArray();
    return dfs(0);
  }
private
  int dfs(int i) {
    if (i >= n) {
      return 0;
    }
    if (f[i] != null) {
      return f[i];
    }
    int[] cnt = new int[26];
    Map<Integer, Integer> freq = new HashMap<>(26);
    int ans = n - i;
    for (int j = i; j < n; ++j) {
      int k = s[j] - 'a';
      if (cnt[k] > 0) {
        if (freq.merge(cnt[k], -1, Integer : : sum) == 0) {
          freq.remove(cnt[k]);
        }
      }
      ++cnt[k];
      freq.merge(cnt[k], 1, Integer : : sum);
      if (freq.size() == 1) {
        ans = Math.min(ans, 1 + dfs(j + 1));
      }
    }
    return f[i] = ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumSubstringsInPartition(string s) {
    int n = s.size();
    int f[n];
    memset(f, -1, sizeof(f));
    function<int(int)> dfs = [&](int i) {
      if (i >= n) {
        return 0;
      }
      if (f[i] != -1) {
        return f[i];
      }
      f[i] = n - i;
      int cnt[26]{};
      unordered_map<int, int> freq;
      for (int j = i; j < n; ++j) {
        int k = s[j] - 'a';
        if (cnt[k]) {
          freq[cnt[k]]--;
          if (freq[cnt[k]] == 0) {
            freq.erase(cnt[k]);
          }
        }
        ++cnt[k];
        ++freq[cnt[k]];
        if (freq.size() == 1) {
          f[i] = min(f[i], 1 + dfs(j + 1));
        }
      }
      return f[i];
    };
    return dfs(0);
  }
};

```

### Python

```python
class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int: @ cache def dfs(i: int) -> int: if i >= n: return 0 cnt = defaultdict(int) freq = defaultdict(int) ans = n - i for j in range(i, n): if cnt[s[j]]: freq[cnt[s[j]]] -= 1 if not freq[cnt[s[j]]]: freq . pop(cnt[s[j]]) cnt[s[j]] += 1 freq[cnt[s[j]]] += 1 if len(freq) == 1 and (t: = 1 + dfs(j + 1)) < ans: ans = t return ans n = len(s) return dfs(0)

```