网站建设 推广 公司,凡科互动小游戏辅助,东莞企业营销型网站建设,百度识图在线使用文章目录1. 题目2. 解题1. 题目
给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern #xff0c;两者都只包含小写英文字母。
你可以在 text 中任意位置插入 一个 字符#xff0c;这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注…
文章目录1. 题目2. 解题1. 题目
给你一个下标从 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 10^5
pattern.length 2
text 和 pattern 都只包含小写英文字母。来源力扣LeetCode 链接https://leetcode-cn.com/problems/maximize-number-of-subsequences-in-a-string 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
首先可以求出每个位置左侧的 0 字符、右侧的 1 字符个数接着求出不插入新字符的情况下有多少种子序列再求出插入一个新字符会增加多少个子序列两者的和就是答案
class Solution {
public:long long maximumSubsequenceCount(string text, string pattern) {int n text.size(), delta 0;long long ans 0;vectorint left0(n), right1(n);for(int i 0; i n; i)left0[i] (i0 ? left0[i-1] : 0) (text[i]pattern[0]);for(int i n-1; i 0; --i)right1[i] (in-1 ? right1[i1] : 0) (text[i]pattern[1]);for(int i 0; i n; i){if(text[i] pattern[1])ans i0 ? left0[i-1] : 0;//原有多少种子序列delta max(delta, max(right1[i], left0[i]));// 增加字符后最大的可能}return ansdelta;}
};76 ms 35.5 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
