目标
给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == "ababcc" 那么 ("abab", "c", "c") ，("ab", "abc", "c") 和 ("ababcc") 都是合法分割，但是 ("a", "bab", "cc") ，("aba", "bc", "c") 和 ("ab", "abcc") 不是，不平衡的子字符串用粗体表示。
请你返回 s 最少 能分割成多少个平衡子字符串。
注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。
示例 1：
输入：s = "fabccddg"
输出：3
解释：
我们可以将 s 分割成 3 个子字符串：("fab, "ccdd", "g") 或者 ("fabc", "cd", "dg") 。示例 2：
输入：s = "abababaccddb"
输出：2
解释：
我们可以将 s 分割成 2 个子字符串：("abab", "abaccddb") 。说明：
- 1 <= s.length <= 1000
- s 只包含小写英文字母。
提示：
- Let dp[i] be the minimum number of partitions for the prefix ending at index i + 1.
- dp[i] can be calculated as the min(dp[j]) over all j such that j < i and word[j+1…i] is valid.
思路
将字符串划分成子字符串，要求子字符串中每个字符的出现次数相同，求划分后子字符串的最少个数。
想了一会没有头绪，暴力求解该如何做？枚举所有可能的划分？分情况讨论，如果划分为两部分有n-1种分发，如果是三部分有C(n-1,2)种，以此类推。这种枚举显然是不可能的。
考虑贪心算法尽可能多的合并？对应示例2，如果前面尽可能多的合并了 ababab 后面的 ac cd db 就要拆开了，并不是最小的。
如何判断给定区间上字符串是平衡的？还是要遍历计数，然后再来一次循环判断个数是否相同。
先将字符串划分为出现次数都是1的子串，然后再进行合并？如何合并？记录 dp[start][end] ？状态如何转移？
看了题解需要使用动态规划，dp[i] 表示 子串 [0 ~ i) 的最小平衡子串的个数。状态转移方程为 for (int j = i; j >= 0; j--) { if (isBlance(word[j, i])) { dp[i+1] = Math.min(dp[j] + 1, dp[i+1])} }
关键点是使用不同字符的种类乘以最大个数直接判断给定区间是否是平衡的，使用循环会超时。
代码
/**
* @date 2024-08-28 10:29
*/
public class MinimumSubstringsInPartition3144 {
public int minimumSubstringsInPartition_v1(String s) {
int n = s.length();
int[] dp = new int[n + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = 0;
int[] cnt = new int[26];
for (int i = 0; i < n; i++) {
Arrays.fill(cnt, 0);
int k = 0, max = 0;
for (int j = i; j >= 0; j--) {
int index = s.charAt(j) - 'a';
k += ++cnt[index] == 1 ? 1 : 0;
max = Math.max(cnt[index], max);
if (k * max == i - j + 1) {
dp[i + 1] = Math.min(dp[j] + 1, dp[i + 1]);
}
}
}
return dp[n];
}
}
性能
