-
发表于 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); } };
- LC 题目链接
-