Hard

题目描述

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

首先，你可以将 s 中最多一个索引位置的字符更改为另一个小写英文字母。

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

  • 选择包含最多 k 个不同字符的 s 的最长前缀。
  • 从 s 中删除该前缀，并将分割数增加 1。s 中剩余的字符（如果有）保持其初始顺序。

通过最优地选择最多一个索引进行更改，返回操作后得到的最大分割数。

示例 1：

输入：s = "accca", k = 2
输出：3
解释：
最优方法是将 s[2] 更改为 a 和 c 以外的字符，例如 b，那么字符串变为 "acbca"。
然后我们执行操作：
- 包含最多 2 个不同字符的最长前缀是 "ac"，删除它，s 变为 "bca"。
- 现在包含最多 2 个不同字符的最长前缀是 "bc"，删除它，s 变为 "a"。
- 最后，删除 "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 <= 10^4
  • s 只包含小写英文字母
  • 1 <= k <= 26

解题思路

这是一道复杂的动态规划和位运算结合的题目。我们需要考虑在最多改变一个字符的情况下，如何获得最多的分割数。

核心思路：

  1. 预计算阶段：首先计算不改变任何字符情况下的分割信息

    • pref[i]：处理 s[0:i] 的分割数
    • suff[i]：处理 s[i:n-1] 的分割数
    • partition_start[i]：包含位置 i 的分割的起始位置

  2. 枚举改变位置：对于每个可能改变的位置 i，尝试所有 25 种可能的替换字符

  3. 计算新分割：当改变位置 i 的字符后，需要重新计算包含该位置的分割：

    • 找到从 partition_start[i] 开始，最多包含 k 个不同字符的最长区间
    • 如果这个区间能够包含位置 i，则形成一个新分割
    • 否则需要考虑分成两个分割的情况

  4. 优化技巧：

    • 使用位运算表示字符集合，快速计算不同字符数量
    • 使用前缀和优化区间查询
    • 通过二分查找快速定位边界

算法流程：

  • 预处理得到原始分割信息
  • 对每个位置枚举所有可能的字符替换
  • 计算替换后的最优分割方案
  • 返回所有方案中的最大分割数

时间复杂度主要来源于枚举位置(O(n))和枚举替换字符(O(25))，每次计算新分割需要O(n)时间。

代码实现

class Solution {
public:
    int maxPartitionsAfterOperations(string s, int k) {
        int n = s.length();
        
        // 计算原始分割信息
        vector<int> pref(n + 1, 0);
        vector<int> suff(n + 1, 0);
        vector<int> partition_start(n);
        
        // 计算前缀分割数
        int mask = 0, start = 0;
        for (int i = 0; i < n; i++) {
            int bit = 1 << (s[i] - 'a');
            mask |= bit;
            partition_start[i] = start;
            
            if (__builtin_popcount(mask) > k) {
                pref[i] = pref[start] + 1;
                start = i;
                mask = bit;
                partition_start[i] = start;
            }
        }
        pref[n] = pref[start] + 1;
        
        // 计算后缀分割数
        mask = 0;
        start = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            int bit = 1 << (s[i] - 'a');
            mask |= bit;
            
            if (__builtin_popcount(mask) > k) {
                suff[i] = suff[start + 1] + 1;
                start = i;
                mask = bit;
            }
        }
        suff[0] = suff[start + 1] + 1;
        
        int maxPartitions = pref[n];
        
        // 尝试改变每个位置的字符
        for (int i = 0; i < n; i++) {
            int ps = partition_start[i];
            
            // 尝试所有可能的替换字符
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == s[i]) continue;
                
                // 计算新的分割
                int newMask = 0;
                int r = ps;
                
                // 找到最长的有效前缀
                for (int j = ps; j < n; j++) {
                    int bit = (j == i) ? (1 << (c - 'a')) : (1 << (s[j] - 'a'));
                    int testMask = newMask | bit;
                    
                    if (__builtin_popcount(testMask) <= k) {
                        newMask = testMask;
                        r = j;
                    } else {
                        break;
                    }
                }
                
                int result;
                if (r >= i) {
                    // 情况1：改变的位置在第一个分割中
                    result = 1 + (ps > 0 ? pref[ps] : 0) + (r + 1 < n ? suff[r + 1] : 0);
                } else {
                    // 情况2：需要两个分割
                    int secondMask = 0;
                    int r2 = r + 1;
                    
                    for (int j = r + 1; j < n; j++) {
                        int bit = (j == i) ? (1 << (c - 'a')) : (1 << (s[j] - 'a'));
                        int testMask = secondMask | bit;
                        
                        if (__builtin_popcount(testMask) <= k) {
                            secondMask = testMask;
                            r2 = j;
                        } else {
                            break;
                        }
                    }
                    
                    result = 2 + (ps > 0 ? pref[ps] : 0) + (r2 + 1 < n ? suff[r2 + 1] : 0);
                }
                
                maxPartitions = max(maxPartitions, result);
            }
        }
        
        return maxPartitions;
    }
};

class Solution:
    def maxPartitionsAfterOperations(self, s: str, k: int) -> int:
        n = len(s)
        
        # 计算原始分割信息
        pref = [0] * (n + 1)
        suff = [0] * (n + 1)
        partition_start = [0] * n
        
        # 计算前缀分割数
        mask = 0
        start = 0
        for i in range(n):
            bit = 1 << (ord(s[i]) - ord('a'))
            mask |= bit
            partition_start[i] = start
            
            if bin(mask).count('1') > k:
                pref[i] = pref[start] + 1
                start = i
                mask = bit
                partition_start[i] = start
        
        pref[n] = pref[start] + 1
        
        # 计算后缀分割数
        mask = 0
        start = n - 1
        for i in range(n - 1, -1, -1):
            bit = 1 << (ord(s[i]) - ord('a'))
            mask |= bit
            
            if bin(mask).count('1') > k:
                suff[i] = suff[start + 1] + 1
                start = i
                mask = bit
        
        suff[0] = suff[start + 1] + 1
        
        max_partitions = pref[n]
        
        # 尝试改变每个位置的字符
        for i in range(n):
            ps = partition_start[i]
            
            # 尝试所有可能的替换字符
            for c in 'abcdefghijklmnopqrstuvwxyz':
                if c == s[i]:
                    continue
                
                # 计算新的分割
                new_mask = 0
                r = ps
                
                # 找到最长的有效前缀
                for j in range(ps, n):
                    bit = (1 << (ord(c) - ord('a'))) if j == i else (1 << (ord(s[j]) - ord('a')))
                    test_mask = new_mask | bit
                    
                    if bin(test_mask).count('1') <= k:
                        new_mask = test_mask
                        r = j
                    else:
                        break
                
                if r >= i:
                    # 情况1：改变的位置在第一个分割中
                    result = 1 + (pref[ps] if ps > 0 else 0) + (suff[r + 1] if r + 1 < n else 0)
                else:
                    # 情况2：需要两个分割
                    second_mask = 0
                    r2 = r + 1
                    
                    for j in range(r + 1, n):
                        bit = (1 << (ord(c) - ord('a'))) if j == i else (1 << (ord(s[j]) - ord('a')))
                        test_mask = second_mask | bit
                        
                        if bin(test_mask).count('1') <= k:
                            second_mask = test_mask
                            r2 = j
                        else:
                            break
                    
                    result = 2 + (pref[ps] if ps > 0 else 0) + (suff[r2 + 1] if r2 + 1 < n else 0)
                
                max_partitions = max(max_partitions, result)
        
        return max_partitions

public class Solution {
    public int MaxPartitionsAfterOperations(string s, int k) {
        int n = s.Length;
        
        // 计算原始分割信息
        int[] pref = new int[n + 1];
        int[] suff = new int[n + 1];
        int[] partitionStart = new int[n];
        
        // 计算前缀分割数
        int mask = 0, start = 0;
        for (int i = 0; i < n; i++) {
            int bit = 1 << (s[i] - 'a');
            mask |= bit;
            partitionStart[i] = start;
            
            if (CountBits(mask) > k) {
                pref[i] = pref[start] + 1;
                start = i;
                mask = bit;
                partitionStart[i] = start;
            }
        }
        pref[n] = pref[start] + 1;
        
        // 计算后缀分割数
        mask = 0;
        start = n - 1;
        for (int i = n - 1; i >= 0; i--) {
            int bit = 1 << (s[i] - 'a');
            mask |= bit;
            
            if (CountBits(mask) > k) {
                suff[i] = suff[start + 1] + 1;
                start = i;
                mask = bit;
            }
        }
        suff[0] = suff[start + 1] + 1;
        
        int maxPartitions = pref[n];
        
        // 尝试改变每个位置的字符
        for (int i = 0; i < n; i++) {
            int ps = partitionStart[i];
            
            // 尝试所有可能的替换字符
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == s[i]) continue;
                
                // 计算新的分割
                int newMask = 0;
                int r = ps;
                
                // 找到最长的有效前缀
                for (int j = ps; j < n; j++) {
                    int bit = (j == i) ? (1 << (c - 'a')) : (1 << (s[j] - 'a'));
                    int testMask = newMask | bit;
                    
                    if (CountBits(testMask) <= k) {
                        newMask = testMask;
                        r = j;
                    } else {
                        break;
                    }
                }
                
                int result;
                if (r >= i) {
                    // 情况1：改变的位置在第一个分割中
                    result = 1 + (ps > 0 ? pref[ps] : 0) + (r + 1 < n ? suff[r + 1] : 0);
                } else {
                    // 情况2：需要两个分割
                    int secondMask = 0;
                    int r2 = r + 1;
                    
                    for (int j = r + 1; j < n; j++) {
                        int bit = (j == i) ? (1 << (c - 'a')) : (1 << (s[j] - 'a'));
                        int testMask = secondMask | bit;
                        
                        if (CountBits(testMask) <= k) {
                            secondMask = testMask;
                            r2 = j;
                        } else {
                            break;
                        }
                    }
                    
                    result = 2 + (ps > 0 ? pref[ps] : 0) + (r2 + 1 < n ? suff[r2 + 1] : 0);
                }
                
                maxPartitions = Math.Max(maxPartitions, result);
            }
        }
        
        return maxPartitions;
    }
    
    private int CountBits(int n) {
        int count = 0;
        while (n > 0) {
            count++;
            n &= (n - 1);
        }
        return count;
    }
}

var maxPartitionsAfterOperations = function(s, k) {
    const n = s.length;
    
    function countPartitions(str) {
        let partitions = 0;
        let i = 0;
        
        while (i < str.length) {
            const seen = new Set();
            let j = i;
            
            while (j < str.length && (seen.has(str[j]) || seen.size < k)) {
                seen.add(str[j]);
                j++;
            }
            
            partitions++;
            i = j;
        }
        
        return partitions;
    }
    
    const originalPartitions = countPartitions(s);
    let maxPartitions = originalPartitions;
    
    for (let i = 0; i < n; i++) {
        for (let c = 'a'; c <= 'z'; c++) {
            if (c === s[i]) continue;
            
            const newStr = s.substring(0, i) + c + s.substring(i + 1);
            const partitions = countPartitions(newStr);
            maxPartitions = Math.max(maxPartitions, partitions);
        }
    }
    
    return maxPartitions;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(n² × 26)
空间复杂度O(n)

详细分析：

  • 时间复杂度：预处理阶段 O(n)，枚举每个位置 O(n)，每个位置尝试 25 种字符替换，每次替换需要 O(n) 时间计算新分割
  • 空间复杂度：需要存储前缀分割数、后缀分割数和分割起始位置数组，均为 O(n) 空间

相关题目