12. 最大UCC子串计算

刷题前请喊一遍我们的口号：

• 方法不对，刷题白费。
• 节省时间，精准刷题。

本题难度系数：⭐⭐⭐⭐⭐ 难

问题描述

小 S 有一个由字符 ‘U’ 和 ‘C’ 组成的字符串 S，并希望在编辑距离不超过给定值 m 的条件下，尽可能多地在字符串中找到 “UCC” 子串。

编辑距离定义为将字符串 S 转化为其他字符串时所需的最少编辑操作次数。允许的每次编辑操作是插入、删除或替换单个字符。你需要计算在给定的编辑距离限制 m 下，能够包含最多 “UCC” 子串的字符串可能包含多少个这样的子串。

例如，对于字符串"UCUUCCCCC"和编辑距离限制m = 3，可以通过编辑字符串生成最多包含 3 个"UCC"子串的序列。

约束条件：

• 字符串长度不超过 1000

测试样例

样例 1：

输入：m = 3,s = "UCUUCCCCC"
输出：3

样例 2：

输入：m = 6,s = "U"
输出：2

样例 3：

输入：m = 2,s = "UCCUUU"
输出：2

解释

样例 1：可以将字符串修改为 “UCCUCCUCC”（2 次替换操作，不超过给定值 m = 3），包含 3 个 “UCC” 子串。

样例 2：后面插入 5 个字符 “CCUCC”（5 次插入操作，不超过给定值 m = 6），可以将字符串修改为 “UCCUCC”，包含 2 个 “UCC” 子串。

样例 3：替换最后 2 个字符，可以将字符串修改为 “UCCUCC”，包含 2 个 “UCC” 子串。

解题思路

这个问题可以转化为动态规划问题。我们需要在给定的编辑距离限制下，尽可能多地构造”UCC”子串。每个”UCC”子串需要 3 个字符，因此我们需要考虑如何高效地利用编辑操作来构造这些子串。

1. 问题分析：
   • 每个”UCC”子串需要 3 个字符：’U’、’C’、’C’。
   • 我们需要计算在给定的编辑距离 m 内，最多能构造多少个这样的子串。
   • 构造一个”UCC”子串可能需要 0 到 3 次编辑操作（取决于原字符串中的字符）。
2. 关键观察：
   • 最优解通常是通过尽可能多地构造完整的”UCC”子串。
   • 我们可以将原字符串分成若干个 3 字符的块，每个块尽量变成”UCC”。
   • 对于每个块，计算将其变成”UCC”所需的最小编辑次数。
3. 动态规划状态设计：
   • dp[i][j] 表示处理到第 i 个字符时，使用了 j 次编辑操作，能得到的最大”UCC”子串数量。
   • 我们需要遍历字符串的每个字符，并考虑所有可能的编辑操作。
4. 算法步骤：
   • 初始化 dp 数组，dp[0][0] = 0。
   • 对于每个字符位置 i，遍历所有可能的编辑操作次数 k（0 到 m）。
   • 对于每个可能的 3 字符块，计算将其变成”UCC”所需的编辑次数，并更新 dp 数组。

最优代码实现

function solution(m, s) {
    const n = s.length;
    const dp = Array.from({ length: n + 1 }, () => Array(m + 1).fill(-Infinity));
    dp[0][0] = 0;
    
    for (let i = 0; i <= n; i++) {
        for (let j = 0; j <= m; j++) {
            if (dp[i][j] === -Infinity) continue;
            
            // Try to skip the current character (delete operation)
            if (i + 1 <= n && j + 1 <= m) {
                dp[i + 1][j + 1] = Math.max(dp[i + 1][j + 1], dp[i][j]);
            }
            
            // Try to form a "UCC" substring starting at position i
            if (i + 3 <= n) {
                let cost = 0;
                cost += (s[i] !== 'U') ? 1 : 0;
                cost += (s[i + 1] !== 'C') ? 1 : 0;
                cost += (s[i + 2] !== 'C') ? 1 : 0;
                
                if (j + cost <= m) {
                    dp[i + 3][j + cost] = Math.max(dp[i + 3][j + cost], dp[i][j] + 1);
                }
            } else if (i + 2 <= n) {
                // Handle cases where we have 2 characters left
                let cost = 0;
                cost += (s[i] !== 'U') ? 1 : 0;
                cost += (s[i + 1] !== 'C') ? 1 : 0;
                cost += 1; // Insert 'C'
                
                if (j + cost <= m) {
                    dp[i + 2][j + cost] = Math.max(dp[i + 2][j + cost], dp[i][j] + 1);
                }
            } else if (i + 1 <= n) {
                // Handle cases where we have 1 character left
                let cost = 0;
                cost += (s[i] !== 'U') ? 1 : 0;
                cost += 2; // Insert 'C' and 'C'
                
                if (j + cost <= m) {
                    dp[i + 1][j + cost] = Math.max(dp[i + 1][j + cost], dp[i][j] + 1);
                }
            } else {
                // Handle cases where we have 0 characters left (insert all 3)
                let cost = 3; // Insert 'U', 'C', 'C'
                
                if (j + cost <= m) {
                    dp[i][j + cost] = Math.max(dp[i][j + cost], dp[i][j] + 1);
                }
            }
        }
    }
    
    let maxUCC = 0;
    for (let j = 0; j <= m; j++) {
        maxUCC = Math.max(maxUCC, dp[n][j]);
    }
    
    return maxUCC;
}

function main() {
    console.log(solution(3, "UCUUCCCCC") === 3); // true
    console.log(solution(6, "U") === 2); // true
    console.log(solution(2, "UCCUUU") === 2); // true
}

main();

代码解释

1. 初始化 dp 数组：
   • dp[i][j] 表示处理到第 i 个字符时，使用了 j 次编辑操作，能得到的最大”UCC”子串数量。
   • 初始时，dp[0][0] = 0，表示处理 0 个字符时，使用 0 次编辑操作，能得到 0 个”UCC”子串。
2. 动态规划填充：
   • 对于每个字符位置 i 和编辑操作次数 j，考虑两种情况：
     • 跳过当前字符（删除操作）。
     • 尝试构造一个”UCC”子串，计算所需的编辑操作次数，并更新 dp 数组。
3. 处理边界情况：
   • 当剩余字符不足 3 个时，通过插入操作补全”UCC”子串。
   • 当没有剩余字符时，通过插入操作构造完整的”UCC”子串。
4. 结果提取：
   • 遍历所有可能的编辑操作次数 j，找到最大的”UCC”子串数量。

这个算法的时间复杂度是 O(n*m)，其中 n 是字符串长度，m 是编辑距离限制，能够高效解决问题。

以上关于12. 最大UCC子串计算的文章就介绍到这了，更多相关内容请搜索码云笔记以前的文章或继续浏览下面的相关文章，希望大家以后多多支持码云笔记。