2207.字符串中最多数目的子序列

【LetMeFly】2207.字符串中最多数目的子序列：计数

力扣题目链接：https://leetcode.cn/problems/maximize-number-of-subsequences-in-a-string/

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。

你可以在 text 中任意位置插入 一个 字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。

请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。

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

 

示例 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" 。

 

提示：

• 1 <= text.length <= 105
• pattern.length == 2
• text 和 pattern 都只包含小写英文字母。

解题方法：计数

首先考虑不能往字符串中添加一个字符的情况，应该怎么做呢？

使用两个变量cnt0和cnt1分别记录pattern[0]和pattern[1]出现了多少次，使用ans记录答案数量。

遍历字符串，如果当前字符和pattern[1]相同，那么ans += cnt0（这是因为之前的每个pattern[0]都可以和当前字符组成pattern，并且cnt1 += 1；

如果当前字符和pattern[0]相同，那么cnt0 += 1。

很好，现在考虑可以往字符串中添加一个字符的情况，要把字符加到哪里呢？

如果要添加pattern[0]到字符串中，那么肯定要将pattern[0]添加到字符串开头，这样后面每个pattern[1]都可以和开头新增的这个pattern[0]组成pattern，答案数量增加cnt1（有多少个pattern[1]技能多组成多少个pattern）；

如果要添加pattern[1]到字符串中，那么肯定要添加到字符串尾，这样答案数量就会增加cnt0。

也就是说，往字符串中添加一个字符，最多可以令答案增加max(cnt0, cnt1)。

• 时间复杂度$O(len(text))$
• 空间复杂度$O(1)$

AC代码

C++

typedef long long ll;

class Solution {
public:
    ll maximumSubsequenceCount(string text, string pattern) {
        ll ans = 0;
        ll cnt0= 0, cnt1 = 0;
        for (char c : text) {
            if (c == pattern[1]) {
                cnt1++;
                ans += cnt0;
            }
            if (c == pattern[0]) {
                cnt0++;
            }
        }
        return ans + max(cnt0, cnt1);
    }
};

Go

package main

func maximumSubsequenceCount(text string, pattern string) int64 {
    ans, cnt0, cnt1 := int64(0), int64(0), int64(0)
    for i := range text  {
        if text[i] == pattern[1] {
            ans += cnt0
            cnt1++
        }
        if text[i] == pattern[0] {
            cnt0++
        }
    }
    if cnt0 > cnt1 {
        ans += cnt0
    } else {
        ans += cnt1
    }
    return ans
}

Java

class Solution {
    public long maximumSubsequenceCount(String text, String pattern) {
        long ans = 0, cnt0 = 0, cnt1 = 0;
        for (char c : text.toCharArray()) {
            if (c == pattern.charAt(1)) {
                ans += cnt0;
                cnt1++;
            }
            if (c == pattern.charAt(0)) {
                cnt0++;
            }
        }
        return ans + Math.max(cnt0, cnt1);
    }
}

Python

class Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        ans = cnt0 = cnt1 = 0
        for c in text:
            if c == pattern[1]:
                ans += cnt0
                cnt1 += 1
            if c == pattern[0]:
                cnt0 += 1
        return ans + max(cnt0, cnt1)

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/142497503