What is the core pattern of the "Maximum Number of Subsequences After One Inserting" problem?

The core pattern involves optimizing subsequence counting through precomputation of helper arrays and determining the optimal insertion point for maximizing subsequences of "LCT".

How can I improve my approach to handling large strings in this problem?

To handle large strings efficiently, focus on precomputing subsequences and avoid recalculating values unnecessarily. Use dynamic programming or similar techniques to reduce time complexity.

What is the significance of precomputing arrays in this problem?

Precomputing arrays like preL, preLC, sufT, and sufCT allows you to quickly calculate subsequences from both the left and right sides of the string without redundant operations, speeding up the solution.

Are there any edge cases I should be aware of for this problem?

Yes, edge cases include strings that already have no valid subsequences, and strings where inserting a letter does not increase the number of subsequences, such as when there is no 'L' or 'C' in the string.

How does GhostInterview help with this problem's interview preparation?

GhostInterview helps by breaking down the problem into digestible steps, providing optimized solutions, and guiding users through common pitfalls and efficient algorithmic strategies for the maximum subsequence problem.

#3628

Medium

auto_awesomeMaximum Number of Subsequences After One Inserting core interview pattern

LeetCode 题解工作台

插入一个字母的最大子序列数

给你一个由大写英文字母组成的字符串 s 。你可以在字符串的任意位置（包括字符串的开头或结尾）最多插入一个大写英文字母。返回在最多插入一个字母后，字符串中可以形成的 "LCT" 子序列的最大数量。子序列是从另一个字符串中删除某些字符（可以不删除）且不改变剩余字符顺序后得到的一个…

题目描述

给你一个由大写英文字母组成的字符串 s。

你可以在字符串的任意位置（包括字符串的开头或结尾）最多插入一个 大写英文字母。

返回在 最多插入一个字母 后，字符串中可以形成的 "LCT" 子序列的最大数量。

子序列 是从另一个字符串中删除某些字符（可以不删除）且不改变剩余字符顺序后得到的一个非空字符串。

示例 1：

输入： s = "LMCT"

输出： 2

解释：

可以在字符串 s 的开头插入一个 "L"，变为 "LLMCT"，其中包含 2 个子序列，分别位于下标 [0, 3, 4] 和 [1, 3, 4]。

示例 2：

输入： s = "LCCT"

输出： 4

解释：

可以在字符串 s 的开头插入一个 "L"，变为 "LLCCT"，其中包含 4 个子序列，分别位于下标 [0, 2, 4]、[0, 3, 4]、[1, 2, 4] 和 [1, 3, 4]。

示例 3：

输入： s = "L"

输出： 0

解释：

插入一个字母无法获得子序列 "LCT"，结果为 0。

提示：

1 <= s.length <= 10⁵
s 仅由大写英文字母组成。

lightbulb

解题思路

方法一：枚举

我们可以先计算出原字符串中 "LCT" 的子序列数量，然后考虑插入一个字母的情况。

计算 "LCT" 子序列的数量可以通过遍历字符串来实现。我们可以枚举中间的 "C"，用两个变量 $l$ 和 $r$ 分别维护左右两侧的 "L" 和 "T" 的数量。对于每个 "C"，我们可以计算出它左侧的 "L" 的数量和右侧的 "T" 的数量，从而得到以该 "C" 为中间的 "LCT" 子序列数量为 $l \times r$ ，累加到总数中。

接下来，我们需要考虑插入一个字母的情况。考虑到插入一个 "L" 或 "C" 或 "T" 的情况：

插入一个 "L"，那么我们只需要统计原字符串中 "CT" 的子序列数量。
插入一个 "T"，那么我们只需要统计原字符串中 "LC" 的子序列数量。
插入一个 "C"，那么我们只需要统计原字符串中 "LT" 的子序列数量，这种情况下，我们可以在前面枚举的过程中，维护一个变量 $\textit{mx}$ ，表示当前最大的 $l \times r$ 的值。

最后，我们将原字符串中 "LCT" 的子序列数量加上插入一个字母后的最大子序列数量，得到最终结果。

时间复杂度 $O(n)$ ，其中 $n$ 是字符串的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def numOfSubsequences(self, s: str) -> int:
        def calc(t: str) -> int:
            cnt = a = 0
            for c in s:
                if c == t[1]:
                    cnt += a
                a += int(c == t[0])
            return cnt

        l, r = 0, s.count("T")
        ans = mx = 0
        for c in s:
            r -= int(c == "T")
            if c == "C":
                ans += l * r
            l += int(c == "L")
            mx = max(mx, l * r)
        mx = max(mx, calc("LC"), calc("CT"))
        ans += mx
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate uses precomputation effectively to reduce the complexity of subsequence counting.
question_mark
The solution demonstrates efficient handling of string manipulation and counting.
question_mark
The candidate optimizes the problem using dynamic programming or a similar approach to minimize redundant calculations.

warning

常见陷阱

外企场景

error
Failing to precompute the necessary arrays efficiently may lead to a brute-force solution with higher time complexity.
error
Incorrect handling of subsequence counting, especially at the insertion points, can result in incorrect answers.
error
Overlooking edge cases like strings that already contain no valid subsequences or strings where inserting a letter doesn't change the result.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider the problem where more than one insertion is allowed, which would require modifying the approach to account for multiple insertion points.
arrow_right_alt
Modify the problem to include case-insensitive subsequences, where the letter insertion might be any alphabet character.
arrow_right_alt
Allow insertions at positions that may also change the string's original order, introducing more complexity in subsequence counting.

help

常见问题

外企场景

探索更多题目 →

auto_awesome

继续模式

Maximum Number of Subsequences After One Inserting core interview pattern

用同一解题框架扩展到更多题目。

arrow_forward signal_cellular_alt

同难度题单

中等

按当前难度继续强化稳定输出。

arrow_forward