Every day a Leetcode
题目来源：2207. 字符串中最多数目的子字符串
解法1：贪心 + 一次遍历
设 pattern 的第一个字符为 x，第二个字符为 y。
根据题意，x 插入的位置越靠左，答案的个数越多；y 插入的位置越靠右，答案的个数越多。
那么 x 应置于 text 最左侧，yyy 应置于 text 最右侧。
我们可以遍历 text 来统计答案：每遇到一个 y，就累加左边 x 的个数。
注意特判 x=y 的情况。当两个字符相同时，设 x 的出现次数为 cnt，子字符串的出现次数 = cnt * (cnt + 1) / 2。
代码实现时，放 x 还是放 y 可以一次遍历求出来：
- 放 x 在最左侧：每次遇到 y 都会多算一个 x，因此答案会多 cnt_y 个（cnt_y 是 y 在 text 中的出现次数）。
- 放 y 在最右侧：这个 y 会与 text 的所有 x 组成子序列，因此答案会多 cnt_x 个（cnt_x 是 x 在 text 中的出现次数）。
代码：
/*
* @lc app=leetcode.cn id=2207 lang=cpp
*
* [2207] 字符串中最多数目的子字符串
*/
// @lc code=start
class Solution
{
public:
long long maximumSubsequenceCount(string text, string pattern)
{
char x = pattern[0], y = pattern[1];
if (x == y)
{
long long cnt = count(text.begin(), text.end(), x);
return cnt * (cnt + 1) / 2;
}
long long ans = 0;
int cnt_x = 0, cnt_y = 0;
for (char &c : text)
{
if (c == x)
cnt_x++;
else if (c == y)
{
cnt_y++;
// 每遇到一个 y，就累加左边 x 的个数
ans += cnt_x;
}
}
return ans + max(cnt_x, cnt_y);
}
};
// @lc code=end
结果：
复杂度分析：
时间复杂度：O(n)，其中 n 是字符串 text 的长度。
空间复杂度：O(1)。
