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

输入： s = "fabccddg"
输出： 3
解释：
我们可以将 `s` 分割成 3 个子字符串： `("fab, "ccdd", "g")` 或者 `("fabc", "cd", "dg")` 。

输入： s = "abababaccddb"
输出： 2
解释：
我们可以将 `s` 分割成 2 个子字符串： `("abab", "abaccddb")` 。

首先说明，分割方案是一定存在的，因为单个字母是平衡的，我们一定可以把 $s$ 划分成 $n$ 个平衡子串。

一、寻找子问题

示例 1 的 $s=\text{fabccddg}$，枚举最后一段的长度：

• 最后一段分割出一个长为 $1$ 的子串，即 $\text{g}$，这是平衡的，问题变成剩余字符串 $\text{fabccdd}$ 最少能分割出多少个平衡子串。
• 最后一段分割出一个长为 $2$ 的子串，即 $\text{dg}$，这是平衡的，问题变成剩余字符串 $\text{fabccd}$ 最少能分割出多少个平衡子串。
• ……

在这个过程中，我们只需要知道剩余字符串的长度，因为剩余字符串一定是 $s$ 的一个前缀。

这些问题都是和原问题相似的、规模更小的子问题，可以用递归解决。

注 1：从右往左思考，主要是为了方便把递归翻译成递推。从左往右思考也是可以的。

注 2：动态规划有「选或不选」和「枚举选哪个」两种基本思考方式。在做题时，可根据题目要求，选择适合题目的一种来思考。本题用到的是「枚举选哪个」。

二、状态定义与状态转移方程

根据上面的讨论，我们只需要在递归过程中跟踪以下信息：

• $i$：剩余字符串是 $s[0]$ 到 $s[i]$。

因此，定义状态为 $\text{dfs}(i)$，表示当剩余字符串是 $s[0]$ 到 $s[i]$ 时，最少能分割出多少个平衡子串。

枚举最后一段从 $s[j]$ 到 $s[i]$，如果这个子串是平衡的，那么接下来要解决的问题是：当剩余字符串是 $s[0]$ 到 $s[j-1]$ 时，最少能分割出多少个平衡子串，即 $\text{dfs}(j-1)$。

枚举所有小于等于 $i$ 的 $j$，取 $\text{dfs}(j-1)$ 的最小值，即

其中 $s[j]$ 到 $s[i]$ 是平衡子串。

如何快速判断子串是平衡的呢？

我们可以在倒序枚举 $j$ 的同时，用一个哈希表（或者数组）统计每个字符的出现次数。如果子串中每个字母的出现次数都相等，那么子串是平衡的。

优化：设子串中有 $k$ 种字母，字母出现次数的最大值为 $\text{maxCnt}$。子串是平衡的，当且仅当子串长度 $i-j+1$ 等于 $k\cdot \text{maxCnt}$。

递归边界：$\text{dfs}(-1)=0$。

递归入口：$\text{dfs}(n-1)$，也就是答案。

三、递归搜索 + 保存递归返回值 = 记忆化搜索

考虑到整个递归过程中有大量重复递归调用（递归入参相同）。由于递归函数没有副作用，同样的入参无论计算多少次，算出来的结果都是一样的，因此可以用记忆化搜索来优化：

• 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 $\text{memo}$ 数组中。
• 如果一个状态不是第一次遇到（$\text{memo}$ 中保存的结果不等于 $\text{memo}$ 的初始值），那么可以直接返回 $\text{memo}$ 中保存的结果。

注意：$\text{memo}$ 数组的初始值一定不能等于要记忆化的值！例如初始值设置为 $0$，并且要记忆化的 $\text{dfs}(i)$ 也等于 $0$，那就没法判断 $0$ 到底表示第一次遇到这个状态，还是表示之前遇到过了，从而导致记忆化失效。一般把初始值设置为 $-1$。

本题当 $i\ge 0$ 时，$\text{dfs}(i)$ 一定是正数（因为任意字符串都存在合法分割方案），所以 $\text{memo}$ 数组初始化成 $0$ 也可以。

四、1:1 翻译成递推

我们可以去掉递归中的「递」，只保留「归」的部分，即自底向上计算。

具体来说，$f[i+1]$ 的定义和 $\text{dfs}(i)$ 的定义是一样的，都表示当剩余字符串是 $s[0]$ 到 $s[i]$ 时，最少能分割出多少个平衡子串。这里 $+1$ 是为了把 $\text{dfs}(-1)$ 这个状态也翻译过来，这样我们可以把 $f[0]$ 作为初始值。

相应的递推式（状态转移方程）也和 $\text{dfs}$ 一样：

其中 $s[j]$ 到 $s[i]$ 是平衡子串。

初始值 $f[0]=0$，翻译自递归边界 $\text{dfs}(-1)=0$。

答案为 $f[n]$，翻译自递归入口 $\text{dfs}(n-1)$。

func minimumSubstringsInPartition(s string) int {
	n := len(s)
	f := make([]int, n+1)
	for i := range s {
		f[i+1] = math.MaxInt
		cnt := [26]int{}
		k, maxCnt := 0, 0
		for j := i; j >= 0; j-- {
			b := s[j] - 'a'
			if cnt[b] == 0 {
				k++
			}
			cnt[b]++
			maxCnt = max(maxCnt, cnt[b])
			if i-j+1 == k*maxCnt {
				f[i+1] = min(f[i+1], f[j]+1)
			}
		}
	}
	return f[n]
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

复杂度：

• 时间复杂度：O(N²)
• 空间复杂度：O(N + C)

执行结果：

• 执行耗时:1 ms,击败了40.84 的Go用户
• 内存消耗:2.4 MB,击败了28.50 的Go用户