Kimi k2.6 LeetCode 3003. 执行操作后的最大分割数量 Go实现

以下是 LeetCode 3003. 执行操作后的最大分割数量 的 Go 实现，采用状态压缩 + 记忆化搜索思路。

Go 代码

```go
package main

func maxPartitionsAfterOperations(s string, k int) int {
n := len(s)
// 记忆化：key = (i << 27) | (cur << 1) | t
// i 最大 1e5，cur 最大 2^26，需要更灵活的 key
type state struct {
i int
cur int
t int
}
f := map[state]int{}

var dfs func(i, cur, t int) int
dfs = func(i, cur, t int) int {
if i >= n {
return 1
}

key := state{i, cur, t}
if v, ok := f[key]; ok {
return v
}

v := 1 << (s[i] - 'a')
nxt := cur | v
ans := 0

// 不修改当前字符
if bitCount(nxt) > k {
// 超过 k 个不同字符，开启新分割块
ans = dfs(i+1, v, t) + 1
} else {
ans = dfs(i+1, nxt, t)
}

// 尝试修改当前字符
if t > 0 {
for j := 0; j < 26; j++ {
nxt = cur | (1 << j)
if bitCount(nxt) > k {
ans = max(ans, dfs(i+1, 1<<j, 0)+1)
} else {
ans = max(ans, dfs(i+1, nxt, 0))
}
}
}

f[key] = ans
return ans
}

return dfs(0, 0, 1)
}

func bitCount(x int) int {
cnt := 0
for x > 0 {
cnt++
x &= x - 1
}
return cnt
}

func max(a, b int) int {
if a > b {
return a
}
return b
}
```

关键点说明

要点 说明
位掩码 `cur` 用 int 的 26 个二进制位表示 a-z 字符是否在当前分割块中出现
`bitCount` 计算掩码中 1 的个数，Go 标准库没有内置，手动实现
记忆化 key 用 struct `(i, cur, t)` 作为 map 的 key，Go 的 map 支持 struct key
不修改分支 当前字符加入后若超过 `k` 个不同字符，必须开启新分割块
修改分支 枚举 26 种可能的修改字符，取最优结果

复杂度分析

- 时间复杂度：O(n \times 26 \times 26)，实际有效状态数远小于理论值
- 空间复杂度：O(n \times 26 \times 26)，用于记忆化 map

注意

Go 中没有 `Integer.bitCount()`，需要手动实现。上述实现使用 `x &= x - 1` 的经典位运算技巧来统计 1 的个数，效率较高。