建设网站浩森宇特,开发流程管理,做教育网站用什么颜色,视频直播sdk快速接入目录 2207. 字符串中最多数目的子序列
题目描述#xff1a;
实现代码与解析#xff1a;
遍历#xff1a;
原理思路#xff1a; 2207. 字符串中最多数目的子序列
题目描述#xff1a; 给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 p…目录 2207. 字符串中最多数目的子序列
题目描述
实现代码与解析
遍历
原理思路 2207. 字符串中最多数目的子序列
题目描述 给你一个下标从 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 105pattern.length 2text 和 pattern 都只包含小写英文字母。
实现代码与解析
遍历
class Solution {public long maximumSubsequenceCount(String text, String pattern) {int n text.length();long res 0;int cnt0 0;int cnt1 0;for (int i 0; i n; i) {if (text.charAt(i) pattern.charAt(1)) {cnt1;res cnt0;}if (text.charAt(i) pattern.charAt(0)) {cnt0;}}return res Math.max(cnt0, cnt1);}
}
原理思路 遍历直到遇到p[1]那么就可以和前面的p[0]构成子序列res直接加上前面的p[0]的数量即可。 最后插入一个字符看是p[0]多还是p[1]多加上即可放在前面或者后面构成子序列。 注意点if要先判断p[1]因为有可能p字符串是aa这种重复字符构成的res要加上。
