class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
}
};
3003. 执行操作后的最大分割数量
给你一个下标从 0 开始的字符串 s 和一个整数 k。
你需要执行以下分割操作，直到字符串 s 变为 空：
s 的最长前缀，该前缀最多包含 k 个 不同 字符。s 中保持原来的顺序。执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。
在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。
示例 1：
输入：s = "accca", k = 2 输出：3 解释：在此示例中，为了最大化得到的分割数量，可以将 s[2] 改为 'b'。 s 变为 "acbca"。 按照以下方式执行操作，直到 s 变为空： - 选择最长且至多包含 2 个不同字符的前缀，"acbca"。 - 删除该前缀，s 变为 "bca"。现在分割数量为 1。 - 选择最长且至多包含 2 个不同字符的前缀，"bca"。 - 删除该前缀，s 变为 "a"。现在分割数量为 2。 - 选择最长且至多包含 2 个不同字符的前缀，"a"。 - 删除该前缀，s 变为空。现在分割数量为 3。 因此，答案是 3。 可以证明，分割数量不可能超过 3。
示例 2：
输入：s = "aabaab", k = 3 输出：1 解释：在此示例中，为了最大化得到的分割数量，可以保持 s 不变。 按照以下方式执行操作，直到 s 变为空： - 选择最长且至多包含 3 个不同字符的前缀，"aabaab"。 - 删除该前缀，s 变为空。现在分割数量为 1。 因此，答案是 1。 可以证明，分割数量不可能超过 1。
示例 3：
输入：s = "xxyz", k = 1 输出：4 解释：在此示例中，为了最大化得到的分割数量，可以将 s[1] 改为 'a'。 s 变为 "xayz"。 按照以下方式执行操作，直到 s 变为空： - 选择最长且至多包含 1 个不同字符的前缀，"xayz"。 - 删除该前缀，s 变为 "ayz"。现在分割数量为 1。 - 选择最长且至多包含 1 个不同字符的前缀，"ayz"。 - 删除该前缀，s 变为 "yz"，现在分割数量为 2。 - 选择最长且至多包含 1 个不同字符的前缀，"yz"。 - 删除该前缀，s 变为 "z"。现在分割数量为 3。 - 选择最且至多包含 1 个不同字符的前缀，"z"。 - 删除该前缀，s 变为空。现在分割数量为 4。 因此，答案是 4。 可以证明，分割数量不可能超过 4。
提示：
1 <= s.length <= 104s 只包含小写英文字母。1 <= k <= 26原站题解
golang 解法, 执行用时: 316 ms, 内存消耗: 76.1 MB, 提交时间: 2024-01-14 12:48:41
// 记忆化搜索 + 记录字符集合
func maxPartitionsAfterOperations(s string, k int) int {
n := len(s)
type args struct {
i, mask int
changed bool
}
memo := map[args]int{}
var dfs func(int, int, bool) int
dfs = func(i, mask int, changed bool) (res int) {
if i == n {
return 1
}
a := args{i, mask, changed}
if v, ok := memo[a]; ok { // 之前计算过
return v
}
// 不改 s[i]
bit := 1 << (s[i] - 'a')
newMask := mask | bit
if bits.OnesCount(uint(newMask)) > k {
// 分割出一个子串，这个子串的最后一个字母在 i-1
// s[i] 作为下一段的第一个字母，也就是 bit 作为下一段的 mask 的初始值
res = dfs(i+1, bit, changed) + 1
} else { // 不分割
res = dfs(i+1, newMask, changed)
}
if !changed {
// 枚举把 s[i] 改成 a,b,c,...,z
for j := 0; j < 26; j++ {
newMask := mask | 1<<j
if bits.OnesCount(uint(newMask)) > k {
// 分割出一个子串，这个子串的最后一个字母在 i-1
// j 作为下一段的第一个字母，也就是 1<<j 作为下一段的 mask 的初始值
res = max(res, dfs(i+1, 1<<j, true)+1)
} else { // 不分割
res = max(res, dfs(i+1, newMask, true))
}
}
}
memo[a] = res // 记忆化
return res
}
return dfs(0, 0, false)
}
// 前后缀分离
func maxPartitionsAfterOperations2(s string, k int) int {
if k == 26 {
return 1
}
seg, mask, size := 1, 0, 0
update := func(i int) {
bit := 1 << (s[i] - 'a')
if mask&bit > 0 {
return
}
size++
if size > k {
seg++ // s[i] 在新的一段中
mask = bit
size = 1
} else {
mask |= bit
}
}
n := len(s)
type pair struct{ seg, mask int }
suf := make([]pair, n+1)
for i := n - 1; i >= 0; i-- {
update(i)
suf[i] = pair{seg, mask}
}
ans := seg // 不修改任何字母
seg, mask, size = 1, 0, 0
for i := range s {
p := suf[i+1]
res := seg + p.seg // 情况 3
unionSize := bits.OnesCount(uint(mask | p.mask))
if unionSize < k {
res-- // 情况 1
} else if unionSize < 26 && size == k && bits.OnesCount(uint(p.mask)) == k {
res++ // 情况 2
}
ans = max(ans, res)
update(i)
}
return ans
}
cpp 解法, 执行用时: 4 ms, 内存消耗: 7.4 MB, 提交时间: 2024-01-14 12:47:25
class Solution {
public:
int maxPartitionsAfterOperations(string s, int k) {
if (k == 26) {
return 1;
}
int seg = 1, mask = 0, size = 0;
auto update = [&](int i) {
int bit = 1 << (s[i] - 'a');
if (mask & bit) return;
if (++size > k) {
seg++; // s[i] 在新的一段中
mask = bit;
size = 1;
} else {
mask |= bit;
}
};
int n = s.length();
vector<pair<int, int>> suf(n + 1);
for (int i = n - 1; i >= 0; i--) {
update(i);
suf[i] = {seg, mask};
}
int ans = seg; // 不修改任何字母
seg = 1, mask = 0, size = 0;
for (int i = 0; i < n; i++) {
auto [suf_seg, suf_mask] = suf[i + 1];
int res = seg + suf_seg; // 情况 3
int union_size = __builtin_popcount(mask | suf_mask);
if (union_size < k) {
res--; // 情况 1
} else if (union_size < 26 && size == k && __builtin_popcount(suf_mask) == k) {
res++; // 情况 2
}
ans = max(ans, res);
update(i);
}
return ans;
}
// method 2
int maxPartitionsAfterOperations2(string s, int k) {
unordered_map<long long, int> memo;
function<int(int, int, bool)> dfs = [&](int i, int mask, bool changed) -> int {
if (i == s.length()) {
return 1;
}
long long args_mask = (long long) i << 32 | mask << 1 | changed;
auto it = memo.find(args_mask);
if (it != memo.end()) { // 之前计算过
return it->second;
}
int res;
// 不改 s[i]
int bit = 1 << (s[i] - 'a');
int new_mask = mask | bit;
if (__builtin_popcount(new_mask) > k) {
// 分割出一个子串，这个子串的最后一个字母在 i-1
// s[i] 作为下一段的第一个字母，也就是 bit 作为下一段的 mask 的初始值
res = dfs(i + 1, bit, changed) + 1;
} else { // 不分割
res = dfs(i + 1, new_mask, changed);
}
if (!changed) {
// 枚举把 s[i] 改成 a,b,c,...,z
for (int j = 0; j < 26; j++) {
new_mask = mask | (1 << j);
if (__builtin_popcount(new_mask) > k) {
// 分割出一个子串，这个子串的最后一个字母在 i-1
// j 作为下一段的第一个字母，也就是 1<<j 作为下一段的 mask 的初始值
res = max(res, dfs(i + 1, 1 << j, true) + 1);
} else { // 不分割
res = max(res, dfs(i + 1, new_mask, true));
}
}
}
return memo[args_mask] = res; // 记忆化
};
return dfs(0, 0, false);
}
};
java 解法, 执行用时: 837 ms, 内存消耗: 93.5 MB, 提交时间: 2024-01-14 12:46:18
public class Solution {
private final Map<Long, Integer> memo = new HashMap<>();
public int maxPartitionsAfterOperations(String s, int k) {
return dfs(0, 0, 0, s.toCharArray(), k);
}
private int dfs(int i, int mask, int changed, char[] s, int k) {
if (i == s.length) {
return 1;
}
long argsMask = (long) i << 32 | mask << 1 | changed;
if (memo.containsKey(argsMask)) { // 之前计算过
return memo.get(argsMask);
}
int res;
// 不改 s[i]
int bit = 1 << (s[i] - 'a');
int newMask = mask | bit;
if (Integer.bitCount(newMask) > k) {
// 分割出一个子串，这个子串的最后一个字母在 i-1
// s[i] 作为下一段的第一个字母，也就是 bit 作为下一段的 mask 的初始值
res = dfs(i + 1, bit, changed, s, k) + 1;
} else { // 不分割
res = dfs(i + 1, newMask, changed, s, k);
}
if (changed == 0) {
// 枚举把 s[i] 改成 a,b,c,...,z
for (int j = 0; j < 26; j++) {
newMask = mask | (1 << j);
if (Integer.bitCount(newMask) > k) {
// 分割出一个子串，这个子串的最后一个字母在 i-1
// j 作为下一段的第一个字母，也就是 1<<j 作为下一段的 mask 的初始值
res = Math.max(res, dfs(i + 1, 1 << j, 1, s, k) + 1);
} else { // 不分割
res = Math.max(res, dfs(i + 1, newMask, 1, s, k));
}
}
}
memo.put(argsMask, res); // 记忆化
return res;
}
}
class Solution2 {
private int seg = 1, mask = 0, size = 0;
public int maxPartitionsAfterOperations(String S, int k) {
if (k == 26) {
return 1;
}
char[] s = S.toCharArray();
int n = s.length;
int[] sufSeg = new int[n + 1];
int[] sufMask = new int[n + 1];
for (int i = n - 1; i >= 0; i--) {
update(s[i], k);
sufSeg[i] = seg;
sufMask[i] = mask;
}
int ans = seg; // 不修改任何字母
seg = 1; mask = 0; size = 0;
for (int i = 0; i < n; i++) {
int res = seg + sufSeg[i + 1]; // 情况 3
int unionSize = Integer.bitCount(mask | sufMask[i + 1]);
if (unionSize < k) {
res--; // 情况 1
} else if (unionSize < 26 && size == k && Integer.bitCount(sufMask[i + 1]) == k) {
res++; // 情况 2
}
ans = Math.max(ans, res);
update(s[i], k);
}
return ans;
}
private void update(char c, int k) {
int bit = 1 << (c - 'a');
if ((mask & bit) != 0) {
return;
}
if (++size > k) {
seg++; // c 在新的一段中
mask = bit;
size = 1;
} else {
mask |= bit;
}
}
}
python3 解法, 执行用时: 1220 ms, 内存消耗: 252 MB, 提交时间: 2024-01-14 12:45:23
class Solution:
def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
@cache
def dfs(i: int, mask: int, changed: bool) -> int:
if i == len(s):
return 1
# 不改 s[i]
bit = 1 << (ord(s[i]) - ord('a'))
new_mask = mask | bit
if new_mask.bit_count() > k:
# 分割出一个子串，这个子串的最后一个字母在 i-1
# s[i] 作为下一段的第一个字母，也就是 bit 作为下一段的 mask 的初始值
res = dfs(i + 1, bit, changed) + 1
else: # 不分割
res = dfs(i + 1, new_mask, changed)
if changed:
return res
# 枚举把 s[i] 改成 a,b,c,...,z
for j in range(26):
new_mask = mask | (1 << j)
if new_mask.bit_count() > k:
# 分割出一个子串，这个子串的最后一个字母在 i-1
# j 作为下一段的第一个字母，也就是 1<<j 作为下一段的 mask 的初始值
res = max(res, dfs(i + 1, 1 << j, True) + 1)
else: # 不分割
res = max(res, dfs(i + 1, new_mask, True))
return res
return dfs(0, 0, False)
# 前后缀分离
def maxPartitionsAfterOperations2(self, s: str, k: int) -> int:
if k == 26: return 1
seg, mask, size = 1, 0, 0
def update(i: int) -> None:
nonlocal seg, mask, size
bit = 1 << (ord(s[i]) - ord('a'))
if mask & bit:
return
size += 1
if size > k:
seg += 1 # s[i] 在新的一段中
mask = bit
size = 1
else:
mask |= bit
n = len(s)
suf = [None] * n + [(0, 0)]
for i in range(n - 1, -1, -1):
update(i)
suf[i] = (seg, mask)
ans = seg # 不修改任何字母
seg, mask, size = 1, 0, 0
for i in range(n):
suf_seg, suf_mask = suf[i + 1]
res = seg + suf_seg # 情况 3
union_size = (mask | suf_mask).bit_count()
if union_size < k:
res -= 1 # 情况 1
elif union_size < 26 and size == k and suf_mask.bit_count() == k:
res += 1 # 情况 2
ans = max(ans, res)
update(i)
return ans