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

链接：3144.分割字符频率相等的最少子字符串
难度：Medium
标签：哈希表、字符串、动态规划、计数
简介：请你返回 s 最少 能分割成多少个平衡子字符串。

题解 1 - python

• 编辑时间：2024-08-28
• 执行用时：9615ms
• 内存消耗：16.46MB
• 编程语言：python
• 解法介绍：dp[i]表示以i字符结尾时的最少分割数

class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        n = len(s)
        dp = [inf] * (n + 1)
        dp[0] = 0
        for i in range(1, n + 1):
            dp[i] = dp[i - 1] + 1
            counter = Counter()
            for j in range(i, 0, -1):
                counter[s[j - 1]] += 1
                if len(set(counter.values())) == 1:
                    dp[i] = min(dp[i], dp[j - 1] + 1)
        return dp[-1]