目标
给你一个下标从 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 都只包含小写英文字母。
思路
已知字符串 pattern 包含两个小写英文字符，可以将其中的一个字符插入字符串 text，求插入后最多可以得到多少个个等于 pattern 的子序列。
刚开始想的是根据乘法原理来做，统计字符串中这两个字符出现的次数，cnt1 与 cnt2，插入出现次数较小的字符，可以使子序列个数增加最多。子序列个数为 Math.max(cnt1, cnt2) * (Math.min(cnt1, cnt2) + 1)。
但是这个想法忽略了这种情况，考虑字符串 mpmp，cnt1 = 2, cnt2 = 2，但是子序列个数并不是 4，而是 3，需要减去第二个 m 之前的 p 的个数。我们不妨以 pattern[0] 为终点，统计它前面的 pattern[1] 的个数，将其从结果中减去。
其实这里还有一个漏洞，应该考虑 pattern 这两个字符相同的情况。c(n,2) = n(n - 1)/2，注意实际计算的时候应该将 n 加 1，因为我们插入了一个字符，即 cnt1 * (cnt1 + 1) / 2。
还是存在一个问题，比如 text 中的字符与 pattern 都是由一个相同的字符组成，那么 cnt1 最大值为 10^5，在乘法计算时就会溢出，需要使用long类型。
官网题解的思路是先计算不插入字符时子序列的个数，遇到 pattern[1] 就累加 pattern[0]，同时记录二者的出现次数：
- 如果
pattern[1]出现次数更多，可以在开头插入pattern[0]使得子序列个数增加pattern[1]个 - 如果
pattern[0]出现次数更多，可以在结尾插入pattern[1]使得子序列个数增加pattern[0]个
最后直接将累加结果加上 Math.max(cnt1, cnt2) 即可。
代码
/**
* @date 2024-09-24 8:54
*/
public class MaximumSubsequenceCount2207 {
public long maximumSubsequenceCount(String text, String pattern) {
long cnt1 = 0, cnt2 = 0;
char c1 = pattern.charAt(0), c2 = pattern.charAt(1);
char[] chars = text.toCharArray();
long sub = 0;
for (char c : chars) {
if (c1 == c) {
cnt1++;
sub += cnt2;
} else if (c2 == c) {
cnt2++;
}
}
if (c1 == c2) {
return cnt1 * (cnt1 + 1) / 2;
}
return Math.max(cnt1, cnt2) * (Math.min(cnt1, cnt2) + 1) - sub;
}
}
性能
