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 mainimport ( "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)

在這裏插入圖片描述