题解：‍‬‬‌‌‌⁠⁠‍‌‌‬‌‬⁠⁠12. 最大UCC子串计算 - 飞书云文档

1.题目

问题描述

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

编辑距离定义为将字符串 SS 转化为其他字符串时所需的最少编辑操作次数。允许的每次编辑操作是插入、删除或替换单个字符。你需要计算在给定的编辑距离限制 mm 下，能够包含最多 "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" 子串。

2.思路

• 考虑下编辑距离的三种操作：插入，删除，修改，我们要得到更多的$$UC$$串，插入是最优的操作,删除是完全不操作的， 替换操作完全可以由插入操作代替，解释下为什么
• 以UUC为例，替换操作会改变成UCC, 而插入操作会得到UUCC，多一个字符对构造新的UCC串更优， 比如此时m=3，
  • 采取替换操作只能得到1个UUC -> UCC -> UCCUC，
  • 而插入可以得到两个UUC ->UUCC -> UCCUCC
  • 删除操作完全对答案没有贡献
• 考虑如何操作最优，由上面可知，所有操作均采取插入。那么已经是UCC的串不需要操作，直接记录, 后面插入也不对已经是UCC的串进行操作,因为对这些进行操作完全对答案不优
• 考虑只需要插入一次可以构成UCC的情况有哪些?
  • U*C*在C的前后都可以，那么只要是UC我们就可以花费代价1让ans加一
  • CC在 第一个C前面, 那么只要是CC就行
  • 字符只能使用一次，所有用后要记录字符的使用状态
• 剩下的字符都需要进行两次操作才能得到UCC
• 我们可以使用变量$$cnt$$记录当前已经操作的字符数量，$$n-cn$$就是剩下需要操作两次的字符数量

3.代码

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int solution(int m, std::string s) {
    // PLEASE DO NOT MODIFY THE FUNCTION SIGNATURE
    // write code here
    int n = s.length();
    vector<bool> use(n, false); //来记录每个位置是否被“插入操作”使用过（每个字符只能使用一次）
    int cnt = 0; // 记录已经操作的字符数
    int ans = 0; // 记录可以插入的 "UCC" 子串的数量

    // 第一步：处理已经是 "UCC" 的子串
    // 遍历字符串，从第3个字符开始，检查每一个 3 字符子串是否是 "UCC"
    for (int i = 2; i < n; i++) {
      string t = s.substr(i - 2, 3);
      if (t == "UCC") {
        use[i] = use[i - 1] = use[i - 2] = true;
        cnt += 3; // 更新已经操作的字符数
        ans++; // 插入了一个 "UCC"，计数加一
      }
    }
    // 第二步：处理 "UC" 和 "CC" 的插入
    // 遍历字符串，检查 "UC" 和 "CC" 是否可以插入
    for (int i = 1; i < n; i++) {
      string t = s.substr(i - 1, 2);
      // 如果当前字符对未被使用过，且 m > 0，可以进行插入
      if (!use[i] && !use[i - 1] && m > 0) {
        if (t == "UC" || t == "CC") {
          use[i] = use[i - 1] = true;
          cnt += 2; //更新已经操作的字符数
          ans++; 
          m--;
        }
      }
    }

    // 第三步：处理剩余的字符
    // 每两次操作才能插入一个UCC（即单个字符插入需要两次操作），
    // 可以使用剩余的 m 次操作尽可能多地插入字符
    ans += min(m / 2, n - cnt);
    m -= min(m / 2, n - cnt) * 2;

    // 第四步：处理剩余的 m 次操作
    // 如果 m 大于 2，则每三次操作可以插入一个 "UCC" 子串
    if (m > 2) {
      ans += m / 3;
    }
    return ans; // Placeholder
}
int main() {
    std::cout << (solution(3, "UCUUCCCCC") == 3) << std::endl;
    std::cout << (solution(6, "U") == 2) << std::endl;
    std::cout << (solution(2, "UCCUUU") == 2) << std::endl;
    return 0;
}

方法二：两次动规

def solution(m: int, s: str) -> int:
    # write code here
    n = len(s)
    dp = [[-1] * (m + 1) for _ in range(n + 1)]  # dp[i][e]：前i个字符编辑e次得到的’UCC'子串数量
    dp[0][0] = 0 

    # 第一次动态规划
    # 计算从每个字符开始，为了匹配 "UCC" 产生的最小编辑距离和匹配成功时的长度
    # 每个字符的计算过程都是dp
    match_info = [[] for _ in range(n)]  # match_info[i] = 从s[i]开始，匹配“UCC”的(最小编辑距离，匹配成功时的长度) 
    for i in range(n):
        max_len = min(n - i, 3 + m)  # 从当前字符s[i]开始，匹配成功时可能达到的最大长度
        # 从当前字符s[i]开始，匹配 "UCC" 的最小编辑距离
        dp_match = [[float('inf')] * (max_len + 1) for _ in range(4)] 
        dp_match[0][0] = 0
        for p in range(4):  # 从s[i]开始匹配"UCC" 的进度：‘’->‘U'->'UC'->'UCC’
            for q in range(max_len + 1):  # 匹配过程中划过的长度 = 0,1,...,max_len
                if dp_match[p][q] > m:  # 编辑次数用完了
                    continue
                if p < 3 and q < max_len:  # 保留/替换
                    cost = 0 if s[i + q] == 'UCC'[p] else 1
                    dp_match[p + 1][q + 1] = min(dp_match[p + 1][q + 1], dp_match[p][q] + cost)
                if p < 3:  # 插入
                    dp_match[p + 1][q] = min(dp_match[p + 1][q], dp_match[p][q] + 1)
                if q < max_len:  # 删除
                    dp_match[p][q + 1] = min(dp_match[p][q + 1], dp_match[p][q] + 1)
        # 统计
        for q in range(max_len + 1):
            c = dp_match[3][q]
            match_info[i].append((c, q))  # (编辑距离，匹配长度)

    # 主过程的动态规划：
    for i in range(n + 1):
        for e in range(m + 1):
            if dp[i][e] == -1:
                continue
            if i < n:  # 不尝试匹配 "UCC" --> 直接跳过/删除当前字符
                dp[i + 1][e] = max(dp[i + 1][e], dp[i][e])  # 保留
                if e + 1 <= m:  # 删除
                    dp[i + 1][e + 1] = max(dp[i + 1][e + 1], dp[i][e])            
            if i < n and match_info[i]: # 尝试匹配
                for c, l in match_info[i]:  # 从当前字符串开始匹配‘UCC’的(最小编辑距离，匹配成功时长度)
                    if e + c <= m and i + l <= n:
                        dp[i + l][e + c] = max(dp[i + l][e + c], dp[i][e] + 1)

    # 找到最大匹配数量
    max_substrings = 0
    for e in range(m + 1):
        max_substrings = max(max_substrings, dp[n][e])
    return max_substrings

if __name__ == '__main__':
    print(solution(m=3, s="UCUUCCCCC") == 3)
    print(solution(m=6, s="U") == 2)
    print(solution(m=2, s="UCCUUU") == 2)