3144. 分割字符频率相等的最少子字符串（24.8.28）

题目

题目：
给你一个字符串 s ，你需要将它分割成一个或者更多的平衡子字符串。 比方说，s == "ababcc" 那么 ("abab","c","c") ，("ab","abc","c") 和 ("ababcc") 都是合法分割，但是 ("a","bab","cc") ， ("aba","bc","c") 和 ("ab","abc") 不是，不平衡的子字符串用粗体表示。

请你返回 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 只包含小写英文字母。

解题思路

见代码

代码

/*
要求求最小的分割数，那么就要求每个字串都要达到尽可能长的长度。可以从大到小枚举其长度， 
*/
class Solution {
public:int minimumSubstringsInPartition(string s) {int n=s.size();vector<int> cnt(n);//用于记录遇到的长度//由大到小枚举 子串的长度 auto dfs = [&](auto&& dfs, int i) -> int{if(i<0) return 0;//因为长度不可能小于0int& ans=cnt[i];//将ans初始化为对应i长度的记录值if(ans) return ans;//如果此长度及路过就不在继续ans=INT_MAX;//由于是求最小值，九江ans初始化为最大的值，以便于后面的ans值的更新int h[26]{};//建立字母的哈希值进行对字母的统计,用于判断是否满足平衡的概念int k=0;//统计不同字符的个数int max_h=0;//最大的字符个数//从第 i 小标开始向前查看这个子串是否满足for(int j=i;j>=0;j--){k+=(h[s[j]-'a']++==0);//统计不同字符的个数max_h = max(max_h, h[s[j] - 'a']);//最大的字符个数//子集当中字符个数（暂写为 a） i - j + 1//假设其是平衡的 那么其个数是（暂写为 b） k * max_h//如果 a==b 则说明满足条件，那么将ans更新为最小值if (i - j + 1 == k * max_h){ans=min(ans,dfs(dfs,j-1)+1);//再去深搜下一个长度是否满足 再加上此子集的个数 1}}return ans;};return dfs(dfs,n-1);}
};