class Solution {
public:
long long maximumSubsequenceCount(string text, string pattern) {
}
};
2207. 字符串中最多数目的子字符串
给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。
你可以在 text 中任意位置插入 一个 字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头或者结尾的位置。
请你返回插入一个字符后，text 中最多包含多少个等于 pattern 的 子序列 。
子序列 指的是将一个字符串删除若干个字符后（也可以不删除），剩余字符保持原本顺序得到的字符串。
示例 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 <= 105pattern.length == 2text 和 pattern 都只包含小写英文字母。原站题解
rust 解法, 执行用时: 3 ms, 内存消耗: 2.4 MB, 提交时间: 2024-09-24 09:32:04
impl Solution {
pub fn maximum_subsequence_count(text: String, pattern: String) -> i64 {
let pattern = pattern.as_bytes();
let x = pattern[0];
let y = pattern[1];
let mut ans = 0i64;
let mut cnt_x = 0;
let mut cnt_y = 0;
for c in text.bytes() {
if c == y {
ans += cnt_x as i64;
cnt_y += 1;
}
if c == x {
cnt_x += 1;
}
}
ans + cnt_x.max(cnt_y) as i64
}
}
javascript 解法, 执行用时: 95 ms, 内存消耗: 58.3 MB, 提交时间: 2024-09-24 09:31:04
/**
* @param {string} text
* @param {string} pattern
* @return {number}
*/
var maximumSubsequenceCount = function(text, pattern) {
const [x, y] = pattern;
let ans = 0, cntX = 0, cntY = 0;
for (const c of text) {
if (c === y) {
ans += cntX;
cntY++;
}
if (c === x) {
cntX++;
}
}
return ans + Math.max(cntX, cntY);
};
golang 解法, 执行用时: 16 ms, 内存消耗: 6.3 MB, 提交时间: 2024-09-24 09:30:39
func maximumSubsequenceCount(text, pattern string) (ans int64) {
x, y := pattern[0], pattern[1]
cntX, cntY := 0, 0
for i := range text {
c := text[i]
if c == y {
ans += int64(cntX)
cntY++
}
if c == x {
cntX++
}
}
return ans + int64(max(cntX, cntY))
}
python3 解法, 执行用时: 132 ms, 内存消耗: 16.9 MB, 提交时间: 2024-09-24 09:30:08
class Solution:
def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
x, y = pattern
ans = cnt_x = cnt_y = 0
for c in text:
if c == y:
ans += cnt_x
cnt_y += 1
if c == x:
cnt_x += 1
return ans + max(cnt_x, cnt_y)
cpp 解法, 执行用时: 36 ms, 内存消耗: 16.3 MB, 提交时间: 2023-07-12 09:40:58
class Solution {
public:
long long maximumSubsequenceCount(string text, string pattern) {
int cnt0 = 0;
int cnt1 = 0;
long long ans = 0;
for (auto &ch : text) {
if (ch == pattern[1]) {
ans += cnt0;
cnt1++;
}
if (ch == pattern[0]) {
cnt0++;
}
}
return ans + max(cnt0, cnt1);
}
};
golang 解法, 执行用时: 12 ms, 内存消耗: 6.3 MB, 提交时间: 2023-07-12 09:40:29
func maximumSubsequenceCount(text, pattern string) (ans int64) {
x, y := pattern[0], pattern[1]
if x == y {
c := int64(strings.Count(text, pattern[:1]))
return c * (c + 1) / 2
}
cx, cy := 0, 0
for i := range text {
if ch := text[i]; ch == x {
cx++
} else if ch == y {
cy++
ans += int64(cx) // 每遇到一个 y，就累加左边 x 的个数
}
}
return ans + int64(max(cx, cy))
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 148 ms, 内存消耗: 16.8 MB, 提交时间: 2023-07-12 09:39:43
# 贪心
class Solution:
def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
if pattern[0] == pattern[1]:
return (cnt := text.count(pattern[0])) * (cnt + 1) >> 1
cnt1, cnt2, ans = text.count(pattern[0]), text.count(pattern[1]), 0
if cnt1 < cnt2: ans = cnt2
else: cnt2 += 1
for c in text:
if c == pattern[0]: ans += cnt2
elif c == pattern[1]: cnt2 -= 1
return ans
java 解法, 执行用时: 9 ms, 内存消耗: 43.4 MB, 提交时间: 2023-07-12 09:36:12
/**
* 贪心思想
* 若pattern="ac"，那么认为在text的开始添加'a'或者在text的结尾添加'c'这两种情况能得到最大值。
* 遍历字符串，并记录初始子序列数量sum，以及'a'和'c'的数量。
* 在开始处添加'a'，则子序列数量=初始子序列数量+'c'的数量。
* 在结尾处添加'c'，则子序列数量=初始子序列数量+'a'的数量。
**/
class Solution {
public long maximumSubsequenceCount(String text, String pattern) {
char front = pattern.charAt(0), back = pattern.charAt(1);
long sum = 0;
int fcnt = 0, bcnt = 0;
// 从后向前遍历，统计pattern[0]和pattenr[1]的数量以及初始子序列数量。
for(int i = text.length() - 1; i >= 0; i--) {
char c = text.charAt(i);
if(c == front) {
sum += bcnt;
fcnt++;
}
if(c == back){
bcnt++;
}
}
// 返回初始子序列数量+新增的子序列数量
return sum + Math.max(bcnt, fcnt);
}
}