我认为您这里真的不需要动态编程。
O （length（ S ））时间的一种方法：
- 遍历 S ，构建频率图（从不同字母A–Z到计数的映射）。对于您的
ABCB
示例，就是A->1 B->2 C->1 D->0 E->0 ... Z->0
，我们可以将其表示为array[1, 2, 1, 0, 0, ..., 0]
。- 我们之所以这样做，是因为我们实际上根本不在乎字母的位置。有没有真正的区别
ABCB
，并ABBC
在每一个可以通过更换他们的被平衡C
用A
。
- 我们之所以这样做，是因为我们实际上根本不在乎字母的位置。有没有真正的区别
- 对数组进行排序。以您的示例为例
[0, 0, ..., 0, 1, 1, 2]
。- 我们之所以这样做，是因为我们实际上并不关心哪个字母是哪个字母。
ABCB
和之间没有真正的区别ABDB
，因为可以通过将一个单字母替换为另一个字母来平衡每个字母。
- 我们之所以这样做，是因为我们实际上并不关心哪个字母是哪个字母。
- 假设字符串是非空的（因为如果为空，则答案仅为0），则最终的平衡字符串将至少包含1个字符，最多包含26个不同的字母。对于介于1到26之间的每个整数 i ，确定要产生具有 i个 不同字母的平衡字符串，需要执行多少个运算：
- 首先，检查length（ S ）是 i 的倍数；如果不是，则不可能，因此请跳至下一个整数。
- 接下来，计算length（ S ） / i，即最终平衡字符串中每个不同字母的计数。
- 为了计算需要执行的操作数，我们将检查所有需要 增加 的计数。（我们可以等效地检查需要 减少 的计数：它们必须匹配。）
- 我们只对排序数组的最后 i个 元素感兴趣。在该点之前的任何元素都表示不会在平衡字符串中出现的字母：或者计数已经为零并将保持不变，或者它们为非零但将减小为零。无论哪种方式，由于我们仅跟踪 增长 ，因此我们可以忽略它们。
- 对于最后一个小于length（ S ） / i的 i 计数，将其相加。该总和是操作数。（请注意，由于对计数进行了排序，因此当您获得的计数大于或等于目标计数时，可以立即退出此内部循环。） __
- 您可以在第一个 i 大于或等于原始 S中 的不同字母的数目之后退出此循环（除了 i的 值，我们不得不跳过这些值，因为它们没有均匀地除以length（ S ））。例如，如果length（ S ）= 100，并且原始字母 S 具有19个不同的字母，则我们只需要考虑 i 高达20。（向埃里克·王（Eric Wang）提示的暗示是根据这些思路提出的。）
- 返回这些总数中最少的26个总数。（请注意，您实际上并不需要存储所有和；您可以跟踪最小值。）
