[M贪心] lc2207. 字符串中最多数目的子序列(模拟+贪心+一次遍历+代码细节+思维)

1. 题目来源

链接：2207. 字符串中最多数目的子序列

2. 题目解析

思路：

• 根据题目很明显可以贪心的去想：
  • 我应该将 p[0] 放到最左边，将 p[1] 放到最右边。
• 然后直接逆序遍历，统计 p[1] 的个数，遇到 p[0] 时，这个 p[0] 就可以和这些 p[1] 都组合成答案，则答案累加起来 p[1] 的个数即可。

基于上述思路，能很快的写出简洁的代码。

一次遍历优化：

• 记 p[0]=x, p[1]=y
• 可以顺序遍历，先判断当前字符是否等于 y，如果等于 y 的话，它只能和前面的所有的 x 组合成答案，此时累加答案即可。
• 同理，判断当前字符是否等于 x，如果等于 x 的话，这个时候就不需要记录答案了，只需要统计 x 出现的次数即可。
• 最终，因为我们可以将 p[0] 安排到最左侧，此时对答案的贡献就是 cnt_y，同理，将 p[1] 安排到最右侧，对答案的贡献为 cnt_x，那么答案即为 res+max(cnt_x, cnt_y)。
• 这里的 res 就是顺序遍历时，遇到任意一个 y，累加在此之前 x 的总和的结果。

注意：

• 基本思路、一次遍历 思路，都涉及到一个答案累计顺序的问题。
• 我们没有对答案 x=y 的情况做特判，那么需要先更新答案，再累加对应字符出现的次数。
• 因为如果先累加对应字符出现次数，再更新答案的话，就会导致同一个字符在更新，而非两个字符。
• 这里的 cnt_x 是当前字符左边的所有 x 字符出现的次数，并不能包含当前字符。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

代码：

常规写法：

class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        typedef long long LL;
        string s1 = string(1, pattern[0]), s2 = "";
        for (char c : text) 
            if (c == pattern[0] || c == pattern[1]) 
                s1 += c, s2 += c;
        s2 += pattern[1];

        int c1 = 0, c2 = 0;
        int n = s1.size();
        LL res1 = 0, res2 = 0;
        for (int i = n - 1; i >= 0; i -- ) {
        	// 没有对 c1、c2 的判断，对答案的累加要放到前面，不然 c 先加后，可能并不能凑成合法字符，只是单个字符而已
            if (s1[i] == pattern[0]) res1 += c1; 
            if (s2[i] == pattern[0]) res2 += c2;
            if (s1[i] == pattern[1]) c1 ++ ;
            if (s2[i] == pattern[1]) c2 ++ ;
        }

        return max(res1, res2);
    }
};

一次遍历：

class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        typedef long long LL;
        int c1 = 0, c2 = 0;
        LL res = 0;
        for (auto c : text) {
            if (c == pattern[1]) {
                res += c1;
                c2 ++ ;
            }

            if (c == pattern[0]) c1 ++ ;
        }

        return res + max(c1, c2);
    }
};