LeetCode 2207. 字符串中最多数目的子字符串（前缀和）

示例 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 都只包含小写英文字母。

class Solution {
public:
    long long maximumSubsequenceCount(string text, string pattern) {
        int n = text.size(), delta = 0;
        long long ans = 0;
        vector<int> left0(n), right1(n);
        for(int i = 0; i < n; ++i)
            left0[i] = (i>0 ? left0[i-1] : 0) + (text[i]==pattern[0]);
        for(int i = n-1; i >= 0; --i)
            right1[i] = (i<n-1 ? right1[i+1] : 0) + (text[i]==pattern[1]);
        for(int i = 0; i < n; ++i)
        {
            if(text[i] == pattern[1])
                ans += i>0 ? left0[i-1] : 0;//原有多少种子序列
            delta = max(delta, max(right1[i], left0[i]));
            // 增加字符后最大的可能
        }
        return ans+delta;
    }
};