Is Maximum Number of Subsequences After One Inserting easy or hard?

The problem is typically classified as Medium difficulty. The main challenge is recognizing that only two insertion choices exist and that counting subsequences efficiently can be done with a single linear scan.

Maximum Number of Subsequences After One Inserting Python/Java solution

Implement a single pass through the string, track how many times the first pattern character appears, and accumulate subsequence counts whenever the second character appears. After the pass, compute the gain from inserting either character and return the maximum possible total. The same logic works in Python, Java, C++, Go, and TypeScript.

How to solve Maximum Number of Subsequences After One Inserting in O(n)?

Scan the string while counting occurrences of the first pattern character. Every time the second character appears, add the number of first characters seen so far to the subsequence count. Then compute two gains: inserting the first character adds pairs with all existing second characters, while inserting the second adds pairs with all existing first characters. Add the larger gain to the original count.

What is the best approach for Maximum Number of Subsequences After One Inserting?

The optimal approach is greedy enumeration combined with prefix counting. Count existing subsequences of the pattern in one pass, then evaluate two insertion options: inserting the first pattern character or the second. The final answer is the original subsequence count plus the maximum additional pairs formed. This runs in O(n) time and O(1) space.

Is Maximum Number of Subsequences After One Inserting asked at Google/Amazon/Meta?

Problems involving subsequence counting, greedy reasoning, and prefix accumulation are common in interviews at companies like Google, Amazon, and Meta. Variants that require maximizing subsequences after modifications to a string appear frequently in coding rounds.

What data structure is used in Maximum Number of Subsequences After One Inserting?

The solution mainly uses simple counters while iterating through the string. Conceptually it relies on string traversal, greedy decision making, and prefix-style accumulation of character frequencies rather than complex data structures.

What is the time complexity of Maximum Number of Subsequences After One Inserting?

The optimal solution runs in O(n) time with O(1) extra space, where n is the length of the string. It performs a single pass to count existing subsequences and simple frequency counts to evaluate the best insertion choice.

Description Hints 3 Solution Video 16:55

3628. Maximum Number of Subsequences After One Inserting

Medium32.4% acceptance1 company

You are given a string s consisting of uppercase English letters.

You are allowed to insert at most one uppercase English letter at any position (including the beginning or end) of the string.

Return the maximum number of "LCT" subsequences that can be formed in the resulting string after at most one insertion.

Example 1:

Input: s = "LMCT"

Output: 2

Explanation:

We can insert a "L" at the beginning of the string s to make "LLMCT", which has 2 subsequences, at indices [0, 3, 4] and [1, 3, 4].

Example 2:

Input: s = "LCCT"

Output: 4

Explanation:

We can insert a "L" at the beginning of the string s to make "LLCCT", which has 4 subsequences, at indices [0, 2, 4], [0, 3, 4], [1, 2, 4] and [1, 3, 4].

Example 3:

Input: s = "L"

Output: 0

Explanation:

Since it is not possible to obtain the subsequence "LCT" by inserting a single letter, the result is 0.

Constraints:

1 <= s.length <= 10⁵
s consists of uppercase English letters.

Asked at 1 company

D. E. Shaw

Topics

Hints open one at a time

Hint 1

Precompute preL, preLC, sufT, and sufCT arrays to count L’s, LC’s, T’s, and CT’s at each position.

Hint 2

Compute base as the sum over all i of preLC[i] * sufT[i].

Hint 3

For each insert position i, compute gains sufCT[i] for ‘L’, preL[i] * sufT[i] for ‘C’, and preLC[i] for ‘T’, and take the maximum of base and base + gain.

16:55

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def numOfSubsequences(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"LMCT"

Input

"LCCT"

Input

"L"

Your code is saved on this device.Solution