张家港网站建设培训班,湖州站内优化seo公司,wordpress主机搭建,包装设计一键生成器2207. 字符串中最多数目的子序列
给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern #xff0c;两者都只包含小写英文字母。
你可以在 text 中任意位置插入 一个 字符#xff0c;这个插入的字符必须是 pattern[0] 或者 pattern[1] 。…2207. 字符串中最多数目的子序列
给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern 两者都只包含小写英文字母。
你可以在 text 中任意位置插入 一个 字符这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意这个字符可以插入在 text 开头或者结尾的位置。
请你返回插入一个字符后text 中最多包含多少个等于 pattern 的 子序列 。
子序列 指的是将一个字符串删除若干个字符后也可以不删除剩余字符保持原本顺序得到的字符串。
数据范围
1 text.length 105pattern.length 2text 和 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);}
};
