【动态规划】3144.分割字符频率相等的最少子字符串

Problem: 3144. 分割字符频率相等的最少子字符串
难度分1917，记录官解的理解

思路

观察题目要求为最少平衡子字符串的划分方法，可以发现如果设子结构dp[i]为截止到i的子字符串的解，对于这个问题：

1. 没有后效性，即已经求解的子问题不受后续决策的影响。
2. 存在最优子结构，即原问题的最优解可以从子问题的最优解构建得来

对于小于i的j，有dp[i] = Math.min(dp[i], dp[j] + 1)，即试图在j+1的位置进行一次划分，如果更优则更新dp[i]的值。

在思考dp问题的时候，需要注意到这种通过尝试更新来求解dp值的方法，很多问题都无法直接断定地从一个子状态更新。这种尝试更新一般来说带着一次遍历的复杂度。

这样，问题就转为了如何判断j+1到i的字符串是否为平衡字符串，若不是平衡字符串则不能更新。最直观的想法是我们维护一个哈希表，通过不断往哈希表里加入元素，并判断某个元素出现的次数是否等于其他所有元素出现的次数，满足即可，这样每次判断都要遍历一遍哈希表。

仔细观察哈希表，我们发现，只需要出现最多次数的元素乘以哈希表的长度等于j+1到i的字符串长度即可，因此可以将时间优化到常数级。

要注意一个性质可能带来的另外其他性质。

复杂度

• 时间复杂度: $O(n^2)$，其中n为数组s长度。
• 空间复杂度: $O(n+C)$，其中n是数组s长度，C是s中的字符数。

Code

class Solution {
    static final int INF = 0x3f3f3f3f;
    public int minimumSubstringsInPartition(String s) {
        int n = s.length();
        int[] d = new int[n + 1];
        Arrays.fill(d, INF);
        d[0] = 0;
        for (int i = 1; i <= n; i++) {
            Map<Character, Integer> occCnt = new HashMap<Character, Integer>();
            int maxCnt = 0;
            for (int j = i; j >= 1; j--) {
                occCnt.put(s.charAt(j - 1), occCnt.getOrDefault(s.charAt(j - 1), 0) + 1);
                maxCnt = Math.max(maxCnt, occCnt.get(s.charAt(j - 1)));
                if (maxCnt * occCnt.size() == (i - j + 1) && d[j - 1] != INF) {
                    d[i] = Math.min(d[i], d[j - 1] + 1);
                }
            }
        }
        return d[n];
    }
}