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

题目

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

---

给你一个下标从 0 开始的字符串 s 和一个整数 k。

你需要执行以下分割操作，直到字符串 s 变为 空：

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

执行操作之 前 ，你可以将 s 中 至多一处 下标的对应字符更改为另一个小写英文字母。

在最优选择情形下改变至多一处下标对应字符后，用整数表示并返回操作结束时得到的最大分割数量。

示例 1：

输入：s = "accca", k = 2
输出：3
解释：在此示例中，为了最大化得到的分割数量，可以将 s[2] 改为 'b'。
s 变为 "acbca"。
按照以下方式执行操作，直到 s 变为空：
- 选择最长且至多包含 2 个不同字符的前缀，"acbca"。
- 删除该前缀，s 变为 "bca"。现在分割数量为 1。
- 选择最长且至多包含 2 个不同字符的前缀，"bca"。
- 删除该前缀，s 变为 "a"。现在分割数量为 2。
- 选择最长且至多包含 2 个不同字符的前缀，"a"。
- 删除该前缀，s 变为空。现在分割数量为 3。
因此，答案是 3。
可以证明，分割数量不可能超过 3。

示例 2：

输入：s = "aabaab", k = 3
输出：1
解释：在此示例中，为了最大化得到的分割数量，可以保持 s 不变。
按照以下方式执行操作，直到 s 变为空： 
- 选择最长且至多包含 3 个不同字符的前缀，"aabaab"。
- 删除该前缀，s 变为空。现在分割数量为 1。
因此，答案是 1。
可以证明，分割数量不可能超过 1。

示例 3：

输入：s = "xxyz", k = 1
输出：4
解释：在此示例中，为了最大化得到的分割数量，可以将 s[1] 改为 'a'。
s 变为 "xayz"。
按照以下方式执行操作，直到 s 变为空：
- 选择最长且至多包含 1 个不同字符的前缀，"xayz"。
- 删除该前缀，s 变为 "ayz"。现在分割数量为 1。
- 选择最长且至多包含 1 个不同字符的前缀，"ayz"。
- 删除该前缀，s 变为 "yz"，现在分割数量为 2。
- 选择最长且至多包含 1 个不同字符的前缀，"yz"。
- 删除该前缀，s 变为 "z"。现在分割数量为 3。
- 选择最且至多包含 1 个不同字符的前缀，"z"。
- 删除该前缀，s 变为空。现在分割数量为 4。
因此，答案是 4。
可以证明，分割数量不可能超过 4。

提示：

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

题解

方法一：

思路

力扣的苟史评判机制，对于c++选手来说经常出现时间复杂度理应能通过的代码却超时的情况，我们经常需要与这种卡常做斗争。正如本题，$O(n|\Sigma|^2logn)$时间复杂度的代码应该能通过，但是并没有。不过如果使用数组替换vector，$O(n|\Sigma|^2logn)$甚至$O(n|\Sigma|^3logn)$的代码都能通过。

本题本人思路，先预处理处一个dp数组，可以O(1)得到后缀能最多分割的串个数。

预处理dp数组可以先求出前缀中各字符出现次数。前缀做差则得到区间中各个字符出现的次数。在固定区间一端，区间变大区间内不同字符的个数不会减少。因此在已经求出dp[i+1..n]的情况下，可以通过二分查找得到从i开始的最长分割串s[i..x]，我们的状态转移则是dp[i] = dp[x+1]+1

然后从前向后模拟分割串，分别记录已经分割好的串个数seg，以及当前正在分割的串的首位置sp,以及当前正在分割的串出现的不同字符数cnt。由于每次分割需要k个不同字符的最长前缀，所以当cnt大于k时则分出一个新串，并将恰好大于k的位置作为新分割的首位置。

在模拟分割的同时，尝试将每个字符改为'a'-'z'中任意字符。假设我们修改了第i个位置的字符s[i]为其他字符，由于sp位置之前已经分好的串不会影响，我们考虑从sp开始分割出的字符串s[sp...x]，x显然会随我们修改s[i]而变化。如果我们能快速找到x，则答案就是seg+1+dp[x+1]。还有一种特殊情况，如果我们把s[i]修改后恰好形成了新串，则是寻找s[i...x]，答案应该是seg+2+dp[x+1]。如何快速求解出x？我们用改进的二分查找，假设s[i]原本字符为a修改后为b，那么对于区间[sp..i]中的a字符需要减少1，而b字符需要增加1。

枚举修改每个位置的字符复杂度$O(n|\Sigma|)$，枚举时二分的复杂度是$O(|\Sigma|logn)$，总时间复杂度是$O(n|\Sigma|^2logn)$。

代码

class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.size();
        int p[n+1][26];
        memset(p, 0, sizeof(p));
        for (int i=1; i<=n; i++) {
            for (int j=0; j<26; j++) {
                p[i][j] = p[i-1][j];
            }
            p[i][s[i-1]-'a']++;
        }

        // s[u..n-1]找到最小x使得s[u..x]内不同字符个数大于等于k
        auto bisect = [&](int u) { 
            int l = u, r = n+1;
            while (l<r) {
                int m = l+r>>1;
                int cnt = 0;
                for (int i=0; i<26; i++) {
                    cnt += p[m][i]-p[u][i] != 0;
                }
                if (cnt>k) r = m;
                else l = m+1;
            }
            return r-1; // real index
        };
        // s[v]从a修改为b， s[u..n-1]找到最小x使得s[u..x]内不同字符大于等于k
        auto bisect2 = [&](int u, int v, int a, int b) { 
            int l = u, r = n+1;
            while (l<r) {
                int m = l+r>>1;
                int add = 0;
                if (v+1<=m) {
                    add = 1;
                }
                int cnt = 0;
                for (int i=0; i<26; i++) {
                    if (add) cnt += p[m][i]-p[u][i]-(i==a)+(i==b) != 0;
                    else cnt += p[m][i]-p[u][i] != 0;
                }
                if (cnt>k) r = m;
                else l = m+1;
            }
            return r-1; // real index
        };
        int dp[n+1];
        memset(dp, 0, sizeof(dp));
        for (int i=n-1; i>=0; i--) {
            dp[i] = dp[bisect(i)]+1;
        }
        int cur[26];
        memset(cur, 0, sizeof(cur));
        int cnt = 0 ; // cnt 当前段不同字符数
        int ans = 0, seg = 0, sp = 0; // seg已经分段的个数，sp当前分段的起点
        for (int i=0; i<n; i++) {
            for (int j=0; j<26; j++) {
                if (cur[j]++ == 0) cnt++;
                if (cnt>k) {
                    ans = max(ans, seg+2+dp[bisect2(i, i, s[i]-'a', j)]);
                } else {
                    ans = max(ans, seg+1+dp[bisect2(sp, i, s[i]-'a', j)]);
                }
                if (--cur[j] == 0) cnt--;

            }
            if (cur[s[i]-'a']++ == 0) cnt++;
            if (cnt>k) {
                for (int x=0; x<26; x++) cur[x] = 0;
                cnt = 0;
                seg++;
                sp = i;
                if (cur[s[i]-'a']++ == 0) cnt++;
            }
        }
        return ans;
    }
};