【LetMeFly】3144.分割字符频率相等的最少子字符串：动态规划+哈希表
力扣题目链接：https://leetcode.cn/problems/minimum-substring-partition-of-equal-character-frequency/
给你一个字符串 s ，你需要将它分割成一个或者更多的 平衡 子字符串。比方说，s == "ababcc" 那么 ("abab", "c", "c") ，("ab", "abc", "c") 和 ("ababcc") 都是合法分割，但是 ("a", "bab", "cc") ，("aba", "bc", "c") 和 ("ab", "abcc") 不是，不平衡的子字符串用粗体表示。
请你返回 s 最少 能分割成多少个平衡子字符串。
注意：一个 平衡 字符串指的是字符串中所有字符出现的次数都相同。
示例 1：
输入：s = "fabccddg"
输出：3
解释：
我们可以将 s 分割成 3 个子字符串：("fab, "ccdd", "g") 或者 ("fabc", "cd", "dg") 。
示例 2：
输入：s = "abababaccddb"
输出：2
解释：
我们可以将 s 分割成 2 个子字符串：("abab", "abaccddb") 。
提示：
1 <= s.length <= 1000s 只包含小写英文字母。
解题方法：动态规划
使用一个动态规划数组$dp$，其中$dp[i]$代表字符串$s$的前$i$个字符最少能分割成多少个平衡子字符串。初始值除了$dp[0]=0$外都是“无穷大”。
接着使用下标$i$从前往后遍历字符串。假设字符串的$j$到$i$子串是平衡字符串，那么有$dp[i + 1] = \min (dp[i + 1], dp[j] + 1)$。
对于一个下标$i$，如何判断是否存在一个$j\lt i$，使得$j$到$i$的子串是平衡字符串呢？我们可以使用$j$从$i$往前开始遍历字符串，并使用一个哈希表统计每个字符出现的次数，再使用两个变量$types$和$maxTimes$分别统计$j$到$i$的子串中字符种类数和字符最大出现次数。如果$字符种类数\times 字符最大出现次数=子串长度$，就说明子串是平衡字符串（每个字符出现次数相等，都是$maxTimes$次）。
- 时间复杂度$O(len(s)^2)$
- 空间复杂度$O(len(s) + C)$，其中$C$是字符种类数，$C=26$
AC代码
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
int minimumSubstringsInPartition(string& s) {
vector<int> dp(s.size() + 1, 1000000);
dp[0] = 0;
unordered_map<char, int> ma;
for (int i = 0; i < s.size(); i++) {
ma.clear();
int types = 0, maxTimes = 0;
for (int j = i; j >= 0; j--) {
maxTimes = max(maxTimes, ++ma[s[j]]);
if (ma[s[j]] == 1) {
types++;
}
if (maxTimes * types == i - j + 1) {
dp[i + 1] = min(dp[i + 1], dp[j] + 1);
}
}
}
return dp.back();
}
};
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| package main
func min(a int, b int) int {
if (a > b) {
return b
}
return a
}
func max(a int, b int) int {
if (a < b) {
return b
}
return a
}
func minimumSubstringsInPartition(s string) int {
dp := make([]int, len(s) + 1)
for i := range dp {
dp[i] = 100000
}
dp[0] = 0
for i := range s {
ma := map[byte]int{}
types, maxTimes := 0, 0
for j := i; j >= 0; j-- {
ma[s[j]]++
maxTimes = max(maxTimes, ma[s[j]])
if ma[s[j]] == 1 {
types++
}
if types * maxTimes == i - j + 1 {
dp[i + 1] = min(dp[i + 1], dp[j] + 1)
}
}
}
return dp[len(s)]
}
|
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| import java.util.Map;
import java.util.HashMap;
import java.util.Arrays;
class Solution {
public int minimumSubstringsInPartition(String s) {
int[] dp = new int[s.length() + 1];
Arrays.fill(dp, 100000);
dp[0] = 0;
Map<Character, Integer> ma = new HashMap<Character, Integer>();
for (int i = 0; i < s.length(); i++) {
ma.clear();
int types = 0, maxTimes = 0;
for (int j = i; j >= 0; j--) {
int originalTimes = ma.getOrDefault(s.charAt(j), 0);
ma.put(s.charAt(j), originalTimes + 1);
maxTimes = Math.max(maxTimes, originalTimes + 1);
if (originalTimes == 0) {
types++;
}
if (maxTimes * types == i - j + 1) {
dp[i + 1] = Math.min(dp[i + 1], dp[j] + 1);
}
}
}
return dp[s.length()];
}
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| from collections import defaultdict
class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
dp = [100000] * (len(s) + 1)
dp[0] = 0
ma = defaultdict(int)
for i in range(len(s)):
ma.clear()
types, maxTimes = 0, 0
for j in range(i, -1, -1):
ma[s[j]] += 1
maxTimes = max(maxTimes, ma[s[j]])
if ma[s[j]] == 1:
types += 1
if maxTimes * types == i - j + 1:
dp[i + 1] = min(dp[i + 1], dp[j] + 1)
return dp[-1]
|
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/141652980