What is the primary strategy for solving the "Maximize Number of Subsequences in a String" problem?

The primary strategy involves applying a greedy approach combined with prefix sum calculations to determine the best position to insert a character from the pattern, maximizing the subsequences formed.

How do prefix sums help in the solution of this problem?

Prefix sums enable efficient tracking of subsequences across the string, allowing the solution to calculate subsequences formed after character insertion without re-scanning the string multiple times.

What are some common mistakes candidates make while solving this problem?

Common mistakes include failing to insert the pattern character at the optimal position, miscounting subsequences, and neglecting edge cases like inserting at the beginning or end of the string.

What if the pattern contains the same character twice? Does the approach change?

The approach remains similar even if the pattern contains duplicate characters, but it’s crucial to track how each position contributes to the subsequences formed to avoid errors in counting.

How can GhostInterview help me with greedy choice-based problems?

GhostInterview provides insights into greedy strategy applications, offering guidance on making optimal decisions for subsequence problems and helping you identify the best choices for inserting characters.

#2207

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

字符串中最多数目的子序列

给你一个下标从 0 开始的字符串 text 和另一个下标从 0 开始且长度为 2 的字符串 pattern ，两者都只包含小写英文字母。你可以在 text 中任意位置插入一个字符，这个插入的字符必须是 pattern[0] 或者 pattern[1] 。注意，这个字符可以插入在 text 开头…

字符串贪心前缀和

题目描述

给你一个下标从 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 <= 10⁵
pattern.length == 2
text 和 pattern 都只包含小写英文字母。

lightbulb

解题思路

方法一：遍历 + 计数

我们可以使用两个变量 $x$ 和 $y$ 分别记录当前字符串中 $\textit{pattern}[0]$ 和 $\textit{pattern}[1]$ 出现的次数。

然后遍历字符串 $\textit{text}$ ，对于当前遍历到的字符 $c$ ：

如果 $c$ 等于 $\textit{pattern}[1]$ ，我们将 $y$ 加一，此时之前出现过的所有 $\textit{pattern}[0]$ 都可以和当前的 $c$ 组成一个 $\textit{pattern}$ 子序列，因此答案加上 $x$ ；
如果 $c$ 等于 $\textit{pattern}[0]$ ，我们将 $x$ 加一。

遍历结束后，由于我们可以插入一个字符，因此，如果我们在字符串开头加上 $\textit{pattern}[0]$ ，那么可以得到 $y$ 个 $\textit{pattern}$ 子序列；如果我们在字符串结尾加上 $\textit{pattern}[1]$ ，那么可以得到 $x$ 个 $\textit{pattern}$ 子序列。因此，我们将答案加上 $x$ 和 $y$ 中的较大值即可。

时间复杂度 $O(n)$ ，其中 $n$ 为字符串 $\textit{text}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maximumSubsequenceCount(self, text: str, pattern: str) -> int:
        ans = x = y = 0
        for c in text:
            if c == pattern[1]:
                y += 1
                ans += x
            if c == pattern[0]:
                x += 1
        ans += max(x, y)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate effectively demonstrates the ability to apply a greedy approach for subsequences.
question_mark
The candidate uses prefix sums or dynamic counting to reduce time complexity in their solution.
question_mark
The candidate ensures the optimal placement of characters using invariant validation, avoiding suboptimal solutions.

warning

常见陷阱

外企场景

error
Not considering the best position to insert the character, which leads to suboptimal solutions.
error
Failing to handle edge cases such as when inserting at the beginning or end of the string.
error
Misunderstanding how subsequences are counted and invalidating potential subsequences after insertion.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What happens if the pattern length is greater than 2?
arrow_right_alt
Can the pattern contain repeated characters and still maintain the same approach?
arrow_right_alt
What if the pattern length increases dynamically during the insertion?

help

常见问题

外企场景

继续练习

#2209 用地毯覆盖后的最少白色砖块 #2193 得到回文串的最少操作次数 #2222 选择建筑的方案数