跳转至

3003. 执行操作后的最大分割数量

题目描述

给定一个字符串 s 和一个整数 k。

首先，你最多可以更改 s 中的 一处 下标对应字符为另一个小写英文字母。

之后，执行以下分割操作，直到 s 变为 空串：

  • 选择 s 的最长 前缀，该前缀最多包含 k 个 不同 字符。
  • 从 s 中 删除 这个前缀，并将分割数量加一。如果有剩余字符，它们在 s 中保持原来的顺序。

返回一个整数，表示在 最多 改变一处下标对应字符的情况下，经过操作后得到的最大分割数。

 

示例 1：

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

输出：3

解释：

最好的方式是把 s[2] 变为除了 a 和 c 之外的东西，比如 b。然后它变成了 "acbca"。

然后我们执行以下操作：

  1. 最多包含 2 个不同字符的最长前缀是 "ac"，我们删除它然后 s 变为 "bca"。
  2. 现在最多包含 2 个不同字符的最长前缀是 "bc"，所以我们删除它然后 s 变为 "a"。
  3. 最后，我们删除 "a" 并且 s 变成空串，所以该过程结束。

进行操作时，字符串被分成 3 个部分，所以答案是 3。

示例 2：

输入：s = "aabaab", k = 3

输出：1

解释：

一开始 s 包含 2 个不同的字符，所以无论我们改变哪个， 它最多包含 3 个不同字符，因此最多包含 3 个不同字符的最长前缀始终是所有字符，因此答案是 1。

示例 3：

输入：s = "xxyz", k = 1

输出：4

解释：

最好的方式是将 s[0] 或 s[1] 变为 s 中字符以外的东西，例如将 s[0] 变为 w。

然后 s 变为 "wxyz"，包含 4 个不同的字符，所以当 k 为 1，它将分为 4 个部分。

 

提示：

  • 1 <= s.length <= 104
  • s 只包含小写英文字母。
  • 1 <= k <= 26

解法

方法一：记忆化搜索

我们设计一个函数 \(\textit{dfs}(i, \textit{cur}, t)\) 表示当前处理到字符串 \(s\) 的下标 \(i\)，当前前缀中已经包含的字符集合为 \(\textit{cur}\)，并且还可以修改 \(t\) 次字符时，能够得到的最大分割数量。那么答案即为 \(\textit{dfs}(0, 0, 1)\)。

函数 \(\textit{dfs}(i, \textit{cur}, t)\) 的执行逻辑如下：

  1. 如果 \(i \geq n\)，说明已经处理完字符串 \(s\)，返回 1。
  2. 计算当前字符 \(s[i]\) 对应的位掩码 \(v = 1 \ll (s[i] - 'a')\)，并计算更新后的字符集合 \(\textit{nxt} = \textit{cur} \mid v\)。
  3. 如果 \(\textit{nxt}\) 中的位数超过 \(k\)，说明当前前缀已经包含超过 \(k\) 个不同字符，我们需要进行一次分割，此时分割数量加 1，并递归调用 \(\textit{dfs}(i + 1, v, t)\)；否则，继续递归调用 \(\textit{dfs}(i + 1, \textit{nxt}, t)\)。
  4. 如果 \(t > 0\)，说明我们还可以修改一次字符。我们尝试将当前字符 \(s[i]\) 修改为任意一个小写字母（共 26 种选择），对于每个选择，计算更新后的字符集合 \(\textit{nxt} = \textit{cur} \mid (1 \ll j)\)，并根据是否超过 \(k\) 个不同字符，选择相应的递归调用方式，更新最大分割数量。
  5. 使用哈希表缓存已经计算过的状态，避免重复计算。

时间复杂度 \(O(n \times |\Sigma| \times k)\)，空间复杂度 \(O(n \times |\Sigma| \times k)\)。其中 \(n\) 为字符串 \(s\) 的长度，而 \(|\Sigma|\) 为字符集大小。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        @cache
        def dfs(i: int, cur: int, t: int) -> int:
            if i >= n:
                return 1
            v = 1 << (ord(s[i]) - ord("a"))
            nxt = cur | v
            if nxt.bit_count() > k:
                ans = dfs(i + 1, v, t) + 1
            else:
                ans = dfs(i + 1, nxt, t)
            if t:
                for j in range(26):
                    nxt = cur | (1 << j)
                    if nxt.bit_count() > k:
                        ans = max(ans, dfs(i + 1, 1 << j, 0) + 1)
                    else:
                        ans = max(ans, dfs(i + 1, nxt, 0))
            return ans

        n = len(s)
        return dfs(0, 0, 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    private Map<List<Integer>, Integer> f = new HashMap<>();
    private String s;
    private int k;

    public int maxPartitionsAfterOperations(String s, int k) {
        this.s = s;
        this.k = k;
        return dfs(0, 0, 1);
    }

    private int dfs(int i, int cur, int t) {
        if (i >= s.length()) {
            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 = Integer.bitCount(nxt) > k ? dfs(i + 1, v, t) + 1 : 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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.size();
        unordered_map<long long, int> f;
        auto dfs = [&](this auto&& dfs, int i, int cur, int t) -> int {
            if (i >= n) {
                return 1;
            }
            long long key = (long long) i << 32 | cur << 1 | t;
            if (f.count(key)) {
                return f[key];
            }
            int v = 1 << (s[i] - 'a');
            int nxt = cur | v;
            int ans = __builtin_popcount(nxt) > k ? dfs(i + 1, v, t) + 1 : dfs(i + 1, nxt, t);
            if (t) {
                for (int j = 0; j < 26; ++j) {
                    nxt = cur | (1 << j);
                    if (__builtin_popcount(nxt) > k) {
                        ans = max(ans, dfs(i + 1, 1 << j, 0) + 1);
                    } else {
                        ans = max(ans, dfs(i + 1, nxt, 0));
                    }
                }
            }
            return f[key] = ans;
        };
        return dfs(0, 0, 1);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
func maxPartitionsAfterOperations(s string, k int) int {
    n := len(s)
    type tuple struct{ i, cur, t int }
    f := map[tuple]int{}
    var dfs func(i, cur, t int) int
    dfs = func(i, cur, t int) int {
        if i >= n {
            return 1
        }
        key := tuple{i, cur, t}
        if v, ok := f[key]; ok {
            return v
        }
        v := 1 << (s[i] - 'a')
        nxt := cur | v
        var ans int
        if bits.OnesCount(uint(nxt)) > 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 bits.OnesCount(uint(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)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function maxPartitionsAfterOperations(s: string, k: number): number {
    const n = s.length;
    const f: Map<bigint, number> = new Map();
    const dfs = (i: number, cur: number, t: number): number => {
        if (i >= n) {
            return 1;
        }
        const key = (BigInt(i) << 27n) | (BigInt(cur) << 1n) | BigInt(t);
        if (f.has(key)) {
            return f.get(key)!;
        }
        const v = 1 << (s.charCodeAt(i) - 97);
        let nxt = cur | v;
        let ans = 0;
        if (bitCount(nxt) > k) {
            ans = dfs(i + 1, v, t) + 1;
        } else {
            ans = dfs(i + 1, nxt, t);
        }
        if (t) {
            for (let j = 0; j < 26; ++j) {
                nxt = cur | (1 << j);
                if (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.set(key, ans);
        return ans;
    };
    return dfs(0, 0, 1);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

评论