题目描述
给你一个字符串 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 只包含小写英文字母。
解法
方法一：记忆化搜索 + 哈希表
我们设计一个函数 $\textit{dfs}(i)$，表示从字符串 $s[i]$ 开始分割的最少子字符串数量。那么答案就是 $\textit{dfs}(0)$。
函数 $\textit{dfs}(i)$ 的计算过程如下：
如果 $i \geq n$，表示已经处理完了所有字符，返回 $0$。
否则，我们维护一个哈希表 $\textit{cnt}$，表示当前子字符串中每个字符出现的次数。另外，我们还维护一个哈希表 $\textit{freq}$，表示每个字符出现的次数的频率。
然后我们枚举 $j$ 从 $i$ 到 $n-1$，表示当前子字符串的结束位置。对于每个 $j$，我们更新 $\textit{cnt}$ 和 $\textit{freq}$，然后判断 $\textit{freq}$ 的大小是否为 $1$，如果是的话，我们可以从 $j+1$ 开始分割，此时答案为 $1 + \textit{dfs}(j+1)$，我们取所有 $j$ 中答案的最小值作为函数的返回值。
为了避免重复计算，我们使用记忆化搜索。
时间复杂度 $O(n^2)$，空间复杂度 $O(n \times |\Sigma|)$。其中 $n$ 为字符串 $s$ 的长度，而 $|\Sigma|$ 表示字符集的大小，本题中 $|\Sigma| = 26$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
cnt = defaultdict(int)
freq = defaultdict(int)
ans = n - i
for j in range(i, n):
if cnt[s[j]]:
freq[cnt[s[j]]] -= 1
if not freq[cnt[s[j]]]:
freq.pop(cnt[s[j]])
cnt[s[j]] += 1
freq[cnt[s[j]]] += 1
if len(freq) == 1 and (t := 1 + dfs(j + 1)) < ans:
ans = t
return ans
n = len(s)
return dfs(0)
|
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 | class Solution {
private int n;
private char[] s;
private Integer[] f;
public int minimumSubstringsInPartition(String s) {
n = s.length();
f = new Integer[n];
this.s = s.toCharArray();
return dfs(0);
}
private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] != null) {
return f[i];
}
int[] cnt = new int[26];
Map<Integer, Integer> freq = new HashMap<>(26);
int ans = n - i;
for (int j = i; j < n; ++j) {
int k = s[j] - 'a';
if (cnt[k] > 0) {
if (freq.merge(cnt[k], -1, Integer::sum) == 0) {
freq.remove(cnt[k]);
}
}
++cnt[k];
freq.merge(cnt[k], 1, Integer::sum);
if (freq.size() == 1) {
ans = Math.min(ans, 1 + dfs(j + 1));
}
}
return f[i] = ans;
}
}
|
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 | class Solution {
public:
int minimumSubstringsInPartition(string s) {
int n = s.size();
int f[n];
memset(f, -1, sizeof(f));
auto dfs = [&](auto&& dfs, int i) -> int {
if (i >= n) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
f[i] = n - i;
int cnt[26]{};
unordered_map<int, int> freq;
for (int j = i; j < n; ++j) {
int k = s[j] - 'a';
if (cnt[k]) {
freq[cnt[k]]--;
if (freq[cnt[k]] == 0) {
freq.erase(cnt[k]);
}
}
++cnt[k];
++freq[cnt[k]];
if (freq.size() == 1) {
f[i] = min(f[i], 1 + dfs(dfs, j + 1));
}
}
return f[i];
};
return dfs(dfs, 0);
}
};
|
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 | func minimumSubstringsInPartition(s string) int {
n := len(s)
f := make([]int, n)
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != -1 {
return f[i]
}
cnt := [26]int{}
freq := map[int]int{}
f[i] = n - i
for j := i; j < n; j++ {
k := int(s[j] - 'a')
if cnt[k] > 0 {
freq[cnt[k]]--
if freq[cnt[k]] == 0 {
delete(freq, cnt[k])
}
}
cnt[k]++
freq[cnt[k]]++
if len(freq) == 1 {
f[i] = min(f[i], 1+dfs(j+1))
}
}
return f[i]
}
return dfs(0)
}
|
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 | function minimumSubstringsInPartition(s: string): number {
const n = s.length;
const f: number[] = Array(n).fill(-1);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i] !== -1) {
return f[i];
}
const cnt: Map<number, number> = new Map();
const freq: Map<number, number> = new Map();
f[i] = n - i;
for (let j = i; j < n; ++j) {
const k = s.charCodeAt(j) - 97;
if (freq.has(cnt.get(k)!)) {
freq.set(cnt.get(k)!, freq.get(cnt.get(k)!)! - 1);
if (freq.get(cnt.get(k)!) === 0) {
freq.delete(cnt.get(k)!);
}
}
cnt.set(k, (cnt.get(k) || 0) + 1);
freq.set(cnt.get(k)!, (freq.get(cnt.get(k)!) || 0) + 1);
if (freq.size === 1) {
f[i] = Math.min(f[i], 1 + dfs(j + 1));
}
}
return f[i];
};
return dfs(0);
}
|
方法二：记忆化搜索（优化）
我们可以对方法一进行优化，不需要维护 $\textit{freq}$ 哈希表，只需要维护一个哈希表 $\textit{cnt}$，表示当前子字符串中每个字符出现的次数。另外，维护两个变量 $k$ 和 $m$ 分别表示当前子字符串中的字符种类数和出现次数最多的字符的出现次数。对于一个子串 $s[i..j]$，如果 $j-i+1 = m \times k$，那么这个子串就是一个平衡子串。
时间复杂度 $O(n^2)$，空间复杂度 $O(n \times |\Sigma|)$。其中 $n$ 为字符串 $s$ 的长度，而 $|\Sigma|$ 表示字符集的大小，本题中 $|\Sigma| = 26$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
@cache
def dfs(i: int) -> int:
if i >= n:
return 0
cnt = defaultdict(int)
m = 0
ans = n - i
for j in range(i, n):
cnt[s[j]] += 1
m = max(m, cnt[s[j]])
if j - i + 1 == m * len(cnt):
ans = min(ans, 1 + dfs(j + 1))
return ans
n = len(s)
ans = dfs(0)
dfs.cache_clear()
return ans
|
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 | class Solution {
private int n;
private char[] s;
private Integer[] f;
public int minimumSubstringsInPartition(String s) {
n = s.length();
f = new Integer[n];
this.s = s.toCharArray();
return dfs(0);
}
private int dfs(int i) {
if (i >= n) {
return 0;
}
if (f[i] != null) {
return f[i];
}
int[] cnt = new int[26];
int ans = n - i;
int k = 0, m = 0;
for (int j = i; j < n; ++j) {
k += ++cnt[s[j] - 'a'] == 1 ? 1 : 0;
m = Math.max(m, cnt[s[j] - 'a']);
if (j - i + 1 == k * m) {
ans = Math.min(ans, 1 + dfs(j + 1));
}
}
return f[i] = ans;
}
}
|
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 | class Solution {
public:
int minimumSubstringsInPartition(string s) {
int n = s.size();
int f[n];
memset(f, -1, sizeof(f));
auto dfs = [&](auto&& dfs, int i) -> int {
if (i >= n) {
return 0;
}
if (f[i] != -1) {
return f[i];
}
f[i] = n - i;
int cnt[26]{};
int k = 0, m = 0;
for (int j = i; j < n; ++j) {
k += ++cnt[s[j] - 'a'] == 1 ? 1 : 0;
m = max(m, cnt[s[j] - 'a']);
if (j - i + 1 == k * m) {
f[i] = min(f[i], 1 + dfs(dfs, j + 1));
}
}
return f[i];
};
return dfs(dfs, 0);
}
};
|
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 | func minimumSubstringsInPartition(s string) int {
n := len(s)
f := make([]int, n)
for i := range f {
f[i] = -1
}
var dfs func(int) int
dfs = func(i int) int {
if i >= n {
return 0
}
if f[i] != -1 {
return f[i]
}
cnt := [26]int{}
f[i] = n - i
k, m := 0, 0
for j := i; j < n; j++ {
x := int(s[j] - 'a')
cnt[x]++
if cnt[x] == 1 {
k++
}
m = max(m, cnt[x])
if j-i+1 == k*m {
f[i] = min(f[i], 1+dfs(j+1))
}
}
return f[i]
}
return dfs(0)
}
|
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 | function minimumSubstringsInPartition(s: string): number {
const n = s.length;
const f: number[] = Array(n).fill(-1);
const dfs = (i: number): number => {
if (i >= n) {
return 0;
}
if (f[i] !== -1) {
return f[i];
}
const cnt: number[] = Array(26).fill(0);
f[i] = n - i;
let [k, m] = [0, 0];
for (let j = i; j < n; ++j) {
const x = s.charCodeAt(j) - 97;
k += ++cnt[x] === 1 ? 1 : 0;
m = Math.max(m, cnt[x]);
if (j - i + 1 === k * m) {
f[i] = Math.min(f[i], 1 + dfs(j + 1));
}
}
return f[i];
};
return dfs(0);
}
|
方法三：动态规划
我们可以将记忆化搜索转换为动态规划，定义状态 $f[i]$ 对前 $i$ 个字符进行分割的最少子字符串数量。初始时 $f[0] = 0$，其余 $f[i] = +\infty$ 或者 $f[i] = n$。
接下来我们枚举 $i$ 从 $0$ 到 $n-1$，对于每个 $i$，我们维护一个哈希表 $\textit{cnt}$，表示当前子字符串中每个字符出现的次数。另外，我们维护两个变量 $k$ 和 $m$ 分别表示当前子字符串中的字符种类数和出现次数最多的字符的出现次数。对于一个子串 $s[j..i]$，如果 $i-j+1 = m \times k$，那么这个子串就是一个平衡子串。此时我们可以从 $j$ 开始分割，那么 $f[i+1] = \min(f[i+1], f[j] + 1)$。
最终答案为 $f[n]$。
时间复杂度 $O(n^2)$，空间复杂度 $O(n + |\Sigma|)$。其中 $n$ 为字符串 $s$ 的长度，而 $|\Sigma|$ 表示字符集的大小，本题中 $|\Sigma| = 26$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | class Solution:
def minimumSubstringsInPartition(self, s: str) -> int:
n = len(s)
f = [inf] * (n + 1)
f[0] = 0
for i in range(n):
cnt = defaultdict(int)
m = 0
for j in range(i, -1, -1):
cnt[s[j]] += 1
m = max(m, cnt[s[j]])
if i - j + 1 == len(cnt) * m:
f[i + 1] = min(f[i + 1], f[j] + 1)
return f[n]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public int minimumSubstringsInPartition(String s) {
int n = s.length();
char[] cs = s.toCharArray();
int[] f = new int[n + 1];
Arrays.fill(f, n);
f[0] = 0;
for (int i = 0; i < n; ++i) {
int[] cnt = new int[26];
int k = 0, m = 0;
for (int j = i; j >= 0; --j) {
k += ++cnt[cs[j] - 'a'] == 1 ? 1 : 0;
m = Math.max(m, cnt[cs[j] - 'a']);
if (i - j + 1 == k * m) {
f[i + 1] = Math.min(f[i + 1], 1 + f[j]);
}
}
}
return f[n];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 | class Solution {
public:
int minimumSubstringsInPartition(string s) {
int n = s.size();
vector<int> f(n + 1, n);
f[0] = 0;
for (int i = 0; i < n; ++i) {
int cnt[26]{};
int k = 0, m = 0;
for (int j = i; ~j; --j) {
k += ++cnt[s[j] - 'a'] == 1;
m = max(m, cnt[s[j] - 'a']);
if (i - j + 1 == k * m) {
f[i + 1] = min(f[i + 1], f[j] + 1);
}
}
}
return f[n];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 | func minimumSubstringsInPartition(s string) int {
n := len(s)
f := make([]int, n+1)
for i := range f {
f[i] = n
}
f[0] = 0
for i := 0; i < n; i++ {
cnt := [26]int{}
k, m := 0, 0
for j := i; j >= 0; j-- {
x := int(s[j] - 'a')
cnt[x]++
if cnt[x] == 1 {
k++
}
m = max(m, cnt[x])
if i-j+1 == k*m {
f[i+1] = min(f[i+1], 1+f[j])
}
}
}
return f[n]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | function minimumSubstringsInPartition(s: string): number {
const n = s.length;
const f: number[] = Array(n + 1).fill(n);
f[0] = 0;
for (let i = 0; i < n; ++i) {
const cnt: number[] = Array(26).fill(0);
let [k, m] = [0, 0];
for (let j = i; ~j; --j) {
const x = s.charCodeAt(j) - 97;
k += ++cnt[x] === 1 ? 1 : 0;
m = Math.max(m, cnt[x]);
if (i - j + 1 === k * m) {
f[i + 1] = Math.min(f[i + 1], 1 + f[j]);
}
}
}
return f[n];
}
|