JZX轻语：简
LeetCode 2207 - 字符串中最多数目的子序列
发表于2024年09月24日
枚举左维护右 + 贪心的思路，维护两个变量first_cnt和second_cnt分别统计前面字符串中pattern[0]和pattern[1]的出现次数，然后每遇到一次pattern[1]，就累加一次子序列次数(也就是前面的pattern[0]搭配当前的pattern[1])。最后，最优的插入点会出现在最前面或最后面其一：对于最前面，就插入pattern[0]，此时会和后面所有的pattern[1]结合；最后面的话，就插入pattern[1]，此时会和前面所有的pattern[0]结合。取这两个字符统计次数的最大值，加上已有的子序列数即可。
class Solution {
public:
using LL = long long;
LL maximumSubsequenceCount(string text, string pattern) {
LL first_cnt {0}, second_cnt {0}, ans {0};
for (const auto &ch : text) {
if (ch == pattern[0]) ++first_cnt;
if (ch == pattern[1]) {
++second_cnt;
ans += first_cnt - (pattern[0] == pattern[1] ? 1 : 0);
}
}
return ans + max(first_cnt, second_cnt);
}
};