Medium

题目描述

给你一个字符串 s，你需要将它分割成一个或多个平衡子串。

平衡字符串是指字符串中每个字符出现的次数都相同的字符串。

返回将字符串 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 仅由英文小写字母组成

思路提示：

  • 设 dp[i] 为以索引 i+1 结尾的前缀的最小分割数
  • dp[i] 可以通过所有满足 j < i 且子串 s[j+1...i] 是平衡的 j 来计算 min(dp[j])

解题思路

这是一道经典的动态规划题目。核心思想是枚举所有可能的分割位置，对于每个位置判断当前子串是否为平衡子串。

解题思路：

  1. 动态规划状态定义：设 dp[i] 表示前 i 个字符的最小分割数
  2. 状态转移方程：对于位置 i，枚举所有可能的起始位置 j，如果子串 s[j:i] 是平衡的，则 dp[i] = min(dp[i], dp[j] + 1)
  3. 平衡子串判断：统计子串中每个字符的频次，如果所有字符的频次都相同，则为平衡子串

算法步骤：

  • 初始化 dp 数组，dp[0] = 0（空字符串分割数为0）
  • 对于每个位置 i，枚举所有可能的起始位置 j < i
  • 检查子串 s[j:i] 是否为平衡子串：统计字符频次，判断是否所有字符频次相等
  • 如果是平衡子串，更新 dp[i] = min(dp[i], dp[j] + 1)
  • 返回 dp[n]，其中 n 是字符串长度

时间复杂度为 O(n³)，其中 n 是字符串长度。虽然看起来复杂度较高，但由于字符集大小有限（26个字母），实际运行效果良好。

代码实现

class Solution {
public:
    int minimumSubstringsInPartition(string s) {
        int n = s.length();
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (isBalanced(s, j, i - 1)) {
                    dp[i] = min(dp[i], dp[j] + 1);
                }
            }
        }
        
        return dp[n];
    }
    
private:
    bool isBalanced(const string& s, int start, int end) {
        unordered_map<char, int> freq;
        for (int i = start; i <= end; i++) {
            freq[s[i]]++;
        }
        
        int expectedFreq = freq.begin()->second;
        for (auto& p : freq) {
            if (p.second != expectedFreq) {
                return false;
            }
        }
        return true;
    }
};

class Solution:
    def minimumSubstringsInPartition(self, s: str) -> int:
        n = len(s)
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for i in range(1, n + 1):
            for j in range(i):
                if self.is_balanced(s, j, i - 1):
                    dp[i] = min(dp[i], dp[j] + 1)
        
        return dp[n]
    
    def is_balanced(self, s: str, start: int, end: int) -> bool:
        freq = {}
        for i in range(start, end + 1):
            freq[s[i]] = freq.get(s[i], 0) + 1
        
        frequencies = list(freq.values())
        return len(set(frequencies)) == 1

public class Solution {
    public int MinimumSubstringsInPartition(string s) {
        int n = s.Length;
        int[] dp = new int[n + 1];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                if (IsBalanced(s, j, i - 1)) {
                    dp[i] = Math.Min(dp[i], dp[j] + 1);
                }
            }
        }
        
        return dp[n];
    }
    
    private bool IsBalanced(string s, int start, int end) {
        Dictionary<char, int> freq = new Dictionary<char, int>();
        for (int i = start; i <= end; i++) {
            if (freq.ContainsKey(s[i])) {
                freq[s[i]]++;
            } else {
                freq[s[i]] = 1;
            }
        }
        
        int expectedFreq = freq.Values.First();
        return freq.Values.All(f => f == expectedFreq);
    }
}

var minimumSubstringsInPartition = function(s) {
    const n = s.length;
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    
    function isBalanced(start, end) {
        const freq = {};
        for (let i = start; i <= end; i++) {
            freq[s[i]] = (freq[s[i]] || 0) + 1;
        }
        const counts = Object.values(freq);
        return counts.every(count => count === counts[0]);
    }
    
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j < i; j++) {
            if (isBalanced(j, i - 1)) {
                dp[i] = Math.min(dp[i], dp[j] + 1);
            }
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n³)
空间复杂度O(n)

说明：

  • 时间复杂度：外层循环 O(n)，内层循环 O(n)，判断平衡子串 O(n)，总计 O(n³)
  • 空间复杂度：dp 数组占用 O(n) 空间，哈希表最多存储 26 个字符，为常数空间

相关题目