Kimi k2.6 LeetCode 3003. 执行操作后的最大分割数量 Java实现
以下是 LeetCode 3003. 执行操作后的最大分割数量 的 Java 实现。这道题有两种主流解法：
1. 状态压缩 + 记忆化搜索（代码简洁，但复杂度分析需要仔细理解）
2. 前后缀分解（线性复杂度，实现较复杂）
这里提供两种实现：
---
解法一：状态压缩 + 记忆化搜索（推荐）
核心思路：用 `mask`（位掩码）记录当前分割块中已出现的字符集合，`cur` 表示当前块中不同字符的数量。`t` 标记是否还能修改一个字符。
```java
class Solution {
private Map<List<Integer>, Integer> f = new HashMap<>();
private String s;
private int k;
private int n;
public int maxPartitionsAfterOperations(String s, int k) {
this.s = s;
this.k = k;
this.n = s.length();
return dfs(0, 0, 1);
}
/**
* 记忆化搜索
* @param i 当前处理到的位置
* @param cur 当前分割块的字符掩码（位掩码）
* @param t 是否还能修改一个字符（1=可以，0=已用掉）
* @return 从位置 i 开始能获得的最大分割数
*/
private int dfs(int i, int cur, int t) {
if (i >= n) {
return 1; // 到达末尾，最后一个分割块计数
}
var key = List.of(i, cur, t);
if (f.containsKey(key)) {
return f.get(key);
}
// 当前字符的位掩码
int v = 1 << (s.charAt(i) - 'a');
int nxt = cur | v;
int ans;
// 不修改当前字符
if (Integer.bitCount(nxt) > k) {
// 当前字符加入后超过 k 个不同字符，必须开启新分割块
ans = dfs(i + 1, v, t) + 1;
} else {
// 继续当前分割块
ans = dfs(i + 1, nxt, t);
}
// 尝试修改当前字符（如果还能修改）
if (t > 0) {
for (int j = 0; j < 26; j++) {
nxt = cur | (1 << j);
if (Integer.bitCount(nxt) > k) {
// 修改后需要开启新分割块
ans = Math.max(ans, dfs(i + 1, 1 << j, 0) + 1);
} else {
// 修改后继续当前分割块
ans = Math.max(ans, dfs(i + 1, nxt, 0));
}
}
}
f.put(key, ans);
return ans;
}
}
```
---
解法二：前后缀分解（线性复杂度）
核心思路：修改位置 `i` 的字符只会影响包含 `s[i]` 的那个分割块。预处理左右两侧的分割信息，枚举每个修改位置快速计算。
```java
class Solution {
public int maxPartitionsAfterOperations(String s, int k) {
int n = s.length();
// left[i][0] = s[0..i-1] 的完整分割数
// left[i][1] = s[0..i-1] 最后一个未满块的字符掩码
// left[i][2] = s[0..i-1] 最后一个未满块的不同字符数
int[][] left = new int[n + 1][3];
// right[i][0] = s[i..n-1] 的完整分割数
// right[i][1] = s[i..n-1] 第一个未满块的字符掩码
// right[i][2] = s[i..n-1] 第一个未满块的不同字符数
int[][] right = new int[n + 1][3];
// 预处理左侧
int num = 0, mask = 0, count = 0;
for (int i = 0; i < n; i++) {
int bit = 1 << (s.charAt(i) - 'a');
if ((mask & bit) == 0) { // 新字符
count++;
if (count <= k) {
mask |= bit;
} else {
// 开启新块
num++;
mask = bit;
count = 1;
}
}
left[i + 1][0] = num;
left[i + 1][1] = mask;
left[i + 1][2] = count;
}
// 预处理右侧（反向）
num = 0;
mask = 0;
count = 0;
for (int i = n - 1; i >= 0; i--) {
int bit = 1 << (s.charAt(i) - 'a');
if ((mask & bit) == 0) {
count++;
if (count <= k) {
mask |= bit;
} else {
num++;
mask = bit;
count = 1;
}
}
right[i][0] = num;
right[i][1] = mask;
right[i][2] = count;
}
int maxPartitions = left[n][0] + 1; // 不修改的情况
// 枚举修改位置 i
for (int i = 0; i < n; i++) {
// 默认：左侧完整分割 + 右侧完整分割 + 中间 2 块（修改点单独成块或合并）
int seg = left[i][0] + right[i + 1][0] + 2;
int leftMask = left[i][1];
int rightMask = right[i + 1][1];
int totalMask = leftMask | rightMask;
int totalCount = Integer.bitCount(totalMask);
// 情况1：左右未满块 + 修改后的字符可以合并为 1 块
// 需要 totalCount + 1 <= k（+1 是给修改后的字符留的位置）
if (Math.min(totalCount + 1, 26) <= k) {
seg--; // 合并为 1 块，总分割数减 1
}
// 情况2：左右块都已满（各 k 个字符），且存在一个两者都没出现的字符
// 修改后的字符可以独立成块，使中间区域分裂为 3 块
else if (left[i][2] == k && right[i + 1][2] == k && totalCount < 26) {
seg++; // 分裂为 3 块，总分割数加 1
}
maxPartitions = Math.max(maxPartitions, seg);
}
return maxPartitions;
}
}
```
---
两种解法对比
特性 状态压缩 + 记忆化搜索 前后缀分解
时间复杂度 O(n \times 2^{26}) 表面，实际有效状态 O(n \times 26 \times 26) O(n)
空间复杂度 O(n \times 2^{26}) 表面，实际有效状态有限 O(n)
代码复杂度 简洁，约 40 行 较复杂，约 80 行
核心思想 直接模拟分割过程，枚举修改 利用"修改只影响局部"的性质
关键点说明
- 位掩码 `mask`：用一个 int 的 26 个二进制位表示 a-z 字符是否在当前分割块中出现
- `Integer.bitCount()`：计算掩码中 1 的个数，即不同字符数量
- 记忆化状态：`(i, cur, t)` 表示从位置 `i` 开始，当前块字符掩码为 `cur`，是否还能修改的状态。虽然 `cur` 有 2^{26} 种可能，但实际遍历中有效状态远少于这个数