力扣9.24

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

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

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

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

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

数据范围

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

分析

贪心，可以发现，若pattern[0]越往右放，它所贡献的子序列个数越小（只需要数后面有多少个pattern[1]，因此pattern[0]最优的位置是放在开头，同理pattern[1]最优的位置是放在尾部，考虑这两种情况，求一下有多少子序列，然后取max

代码

typedef long long LL;
class Solution {
public:const static int N = 1e5 + 5;long long maximumSubsequenceCount(string text, string pattern) {int n = text.size();LL res1 = 0, res2 = 0;LL cnt1 = 1, cnt2 = 1;for(int i = 0; i < n; i ++ ) {if(text[i] == pattern[0] || text[i] == pattern[1]) {if(text[i] == pattern[1]) {res1 += cnt1;}if(text[i] == pattern[0]) cnt1 ++ ;}if(text[n - i - 1] == pattern[0] || text[n - i - 1] == pattern[1]) {if(text[n - i - 1] == pattern[0]) {res2 += cnt2;} if(text[n - i - 1] == pattern[1]) cnt2 ++ ;}}return max(res1, res2);}
};