Fewest Substrings with Equal Character Frequencies
Company: Grammarly
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
# Fewest Substrings with Equal Character Frequencies
You are given a lowercase English string `s`. Partition the entire string into one or more nonempty, contiguous substrings, preserving their order.
A substring is **balanced** if every distinct character that appears in it occurs the same number of times. Characters absent from that substring do not affect whether it is balanced.
Return the minimum number of balanced substrings in a partition of `s`.
### Examples
**Example 1**
```text
Input: s = "aabbc"
Output: 2
```
The partition `("aabb", "c")` is valid. The whole string is not balanced because `a` and `b` occur twice while `c` occurs once, so one part is impossible and two is optimal.
**Example 2**
```text
Input: s = "abcbac"
Output: 1
```
The entire string is balanced: `a`, `b`, and `c` each occur twice. Equal characters do not need to be adjacent.
### Constraints
- `1 <= s.length <= 1000`.
- `s` consists only of lowercase English letters.
### Clarifying Questions
- Must every character of `s` appear in exactly one part? Yes; this is a partition of the entire string.
- May a part skip positions or rearrange characters? No; each part is a contiguous substring.
- Is a substring containing only one distinct character balanced? Yes, regardless of its length.
- Should the result contain the actual partition? No; return its minimum number of parts.
### C++ Interface
```cpp
class Solution {
public:
int minimumSubstringsInPartition(string s) {
}
};
```
### Reasoning Checkpoints
- Check equal positive frequencies within each chosen substring.
- Cover the whole string without gaps, overlap or reordering.
- Prove the number of parts is minimal and account for the full length bound.
```hint Consider the last part
Use a prefix dynamic program. For each prefix, consider every balanced suffix that could be its final part. Maintain character counts while extending that suffix backward.
```
Overview: Partition a lowercase string into as few contiguous parts as possible, with equal positive character frequencies in each part. Includes boundary cases and a full C++ solution.