当前位置：首页 > article >正文

【每日一题】LeetCode 2207.字符串中最多数目的子序列（贪心、字符串、前缀和）

article 2024/9/25 1:25:07

【每日一题】LeetCode 2207.字符串中最多数目的子序列（贪心、字符串、前缀和）

题目描述

给定一个字符串 text 和一个长度为2的字符串 pattern，两者都由小写英文字母组成。你可以在 text 中任意位置插入一个字符，这个插入的字符必须是 pattern[0] 或者 pattern[1]。插入后，需要计算 text 中最多可以包含多少个等于 pattern 的子序列。

子序列 定义为：将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。

思路分析

这个问题可以通过动态规划解决，但这里我们使用一种更简单的贪心算法。

理解子序列：首先理解子序列的概念，即 pattern 可以作为 text 的一部分，且顺序不变。
计数：遍历 text，使用两个计数器 cnt1 和 cnt2 分别计数 pattern[0] 和 pattern[1] 在 text 中出现的次数。
贪心策略：对于每个 pattern[1] 的出现，它都可以与之前所有 pattern[0] 的出现组合成 pattern，因此每找到一个 pattern[1]，就将 cnt1 加到答案 ans 中。
插入策略：在遍历结束后，比较 cnt1 和 cnt2 的大小，因为我们可以插入一个字符来增加子序列的数量。插入 pattern[0] 可以增加 cnt2 的数量，插入 pattern[1] 可以增加 cnt1 的数量。
返回答案：最终答案为 ans + Math.max(cnt1, cnt2)。

输入示例

示例 1：

输入：text = "abdcdbc", pattern = "ac"
输出：4
解释：
如果我们在 text[1] 和 text[2] 之间添加 pattern[0] = 'a' ，那么我们得到 "abadcdbc" 。那么 "ac" 作为子序列出现 4 次。
其他得到 4 个 "ac" 子序列的方案还有 "aabdcdbc" 和 "abdacdbc" 。
但是，"abdcadbc" ，"abdccdbc" 和 "abdcdbcc" 这些字符串虽然是可行的插入方案，但是只出现了 3 次 "ac" 子序列，所以不是最优解。
可以证明插入一个字符后，无法得到超过 4 个 "ac" 子序列。

示例 2：

输入：text = "aabb", pattern = "ab"
输出：6
解释：
可以得到 6 个 "ab" 子序列的部分方案为 "aaabb" ，"aaabb" 和 "aabbb"

代码实现

class Solution {
    public long maximumSubsequenceCount(String text, String pattern) {
        char p1 = pattern.charAt(0); // pattern的第一个字符
        char p2 = pattern.charAt(1); // pattern的第二个字符
        long ans = 0; // 初始化答案为0
        int cnt1 = 0; // 用于计数text中pattern[0]出现的次数
        int cnt2 = 0; // 用于计数text中pattern[1]出现的次数
        
        for (char c : text.toCharArray()) { // 遍历text中的每个字符
            if (c == p2) { // 如果当前字符是pattern的第二个字符
                ans += cnt1; // 将cnt1加到答案中，因为每一个pattern[1]都可以与之前的pattern[0]组合
                cnt2++; // 增加pattern[1]的计数
            }
            if (c == p1) { // 如果当前字符是pattern的第一个字符
                cnt1++; // 增加pattern[0]的计数
            }
        }
        // 返回最终答案，即现有的子序列数量加上可以插入一个字符后增加的最大子序列数量
        return ans + Math.max(cnt1, cnt2);
    }
}