发表于 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 题目链接