2024-05-04：用 go 语言，给定一个起始索引为 0 的字符串 s 和一个整数 k。要进行分割操作，直到字符串 s 为空：选择 s 的最长前缀，该前缀最多包含 k 个不同字符；删除该前缀，递增分割计数。如果有剩余

作者：福大大架构师每日一题

2024-05-04
北京
本文字数：1763 字
阅读完需：约 6 分钟

2024-05-04：用 go 语言，给定一个起始索引为 0 的字符串 s 和一个整数 k。

要进行分割操作，直到字符串 s 为空：

选择 s 的最长前缀，该前缀最多包含 k 个不同字符；

删除该前缀，递增分割计数。如果有剩余字符，它们保持原来的顺序。

在操作之前，可以修改字符串 s 中的一个字符为另一个小写英文字母。

在最佳情况下修改至多一次字符后，返回操作结束时得到的最大分割数量。

输入：s = "accca", k = 2。

输出：3。

答案 2024-05-04：

chatgpt

题目来自 leetcode3003。

大体步骤如下：

1.创建一个递归函数dfs，用于计算分割得到的最大数量。

2.函数中，首先检查是否到达字符串末尾，若是则返回 1（表示完成一个分割）。

3.使用memo记录中间结果，加快计算速度。

4.对于当前处理的字符s[i]，如果不将其作为新的分割点，继续处理下一个字符。

5.如果将s[i]作为新的分割点，并且新的字符数量不超过k，则继续向后处理。

6.如果未修改过字符，则尝试修改s[i]为其他 26 个小写字母，然后继续考虑分割带来的最大数量。

7.在每一步中，根据是否修改过字符，记录当前的最大分割数量。

8.最终返回得到的最大分割数量。

总的时间复杂度为 $O (n \cdot 2^{26})$ ，其中 $n$ 为字符串长度， $2^{26}$ 表示尝试修改字符的可能性数目。

总的额外空间复杂度为 $O (n \cdot 2^{26})$ ，主要由memo中间结果记录所占用的空间引起。

Go 完整代码如下：

package main
import (  "fmt"  "math/bits")
func max(x, y int) int {  if x > y {    return x  }  return y}
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 main() {  s := "accca"  k := 2  result := maxPartitionsAfterOperations(s, k)  fmt.Println(result)}

复制代码

Python 完整代码如下：

# -*-coding:utf-8-*-
def max_partitions_after_operations(s, k):    n = len(s)    memo = {}
    def dfs(i, mask, changed):        if i == n:            return 1
        a = (i, mask, changed)        if a in memo:            return memo[a]
        res = 0        bit = 1 << (ord(s[i]) - ord('a'))        new_mask = mask | bit
        if bin(new_mask).count('1') > k:            res = dfs(i + 1, bit, changed) + 1        else:            res = dfs(i + 1, new_mask, changed)
        if not changed:            for j in range(26):                new_mask = mask | 1 << j                if bin(new_mask).count('1') > k:                    res = max(res, dfs(i + 1, 1 << j, True) + 1)                else:                    res = max(res, dfs(i + 1, new_mask, True))
        memo[a] = res        return res
    return dfs(0, 0, False)
s = "accca"k = 2result = max_partitions_after_operations(s, k)print(result)