Maximum Number of Subsequences After One Inserting solution and explanation
7 more videos on this problem
Maximum Number of Subsequences After One Inserting | Leetcode 3628| Weekly Contest 460 | Q2ExpertFunda · 16:55 · 1K views
Leetcode 3628 | Maximum Number of Subsequences After One Inserting deep explanation | Contest 460 Q2Samrat Bhardwaj · 37:28 · 496 views
3628 Maximum Number of Subsequences After One Inserting | Leetcode Weekly Contest 460Break and Build · 37:18 · 472 views
LeetCode 3628. Maximum Number of Subsequences After One Inserting | Prefix && Suffix Array | O(N)Leet's Code · 43:45 · 385 views
3628.Maximum Number of Subsequences After One Inserting LeetCode Weekly 460 C++ Greedy+CombinatoricsBEASTCODES · 15:38 · 211 views
3628. Maximum Number of Subsequences After One Inserting (Leetcode Medium)Programming Live with Larry · 13:26 · 196 views
Leetcode Weekly Contest 460 - Q2. Maximum Number of Subsequences After One InsertingADevOpsEngineer · 18:29 · 187 views
【每日一题】LeetCode 3628. Maximum Number of Subsequences After One InsertingHuifeng Guan · 26:07 · 169 views
The problem
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 <= 105sconsists of uppercase English letters.
Approach overview
Problem Overview: You are given a string s and a two‑character pattern. You may insert exactly one character anywhere in the string. The goal is to maximize how many times the pattern appears as a subsequence after the insertion.
The subsequence condition means characters do not need to be adjacent, only ordered. The key decision is which character to insert and where it contributes the most subsequences. Because the pattern length is fixed at two, the problem reduces to counting how many valid pairs can be formed.
Approach 1: Brute Force Enumeration (O(n²) time, O(1) space)
Try inserting either character of the pattern at every possible index from 0 to n. After each insertion, scan the entire string and count how many subsequences match the pattern. Counting subsequences can be done by iterating through the string while tracking how many occurrences of the first pattern character have appeared so far. Each time the second character appears, add the current count of the first character. This approach is straightforward but expensive because you repeat the full counting step for every insertion position.
Approach 2: Greedy Enumeration with Prefix Counting (O(n) time, O(1) space)
Observe that inserting the first character of the pattern increases subsequences formed with all existing occurrences of the second character. Inserting the second character increases subsequences formed with all previous occurrences of the first character. Because only two characters are possible insertion choices, you only need to evaluate two scenarios.
First compute the number of subsequences already present in s. Iterate through the string while counting how many times the first pattern character has appeared. Every time the second pattern character appears, add the current count. Then compute the potential gain: inserting the first character at the beginning pairs with every existing second character, while inserting the second character at the end pairs with every existing first character. The maximum of these two options gives the optimal result. This works because the best insertion location always maximizes pair formation globally rather than locally.
This solution relies on linear scans and simple counters. The idea closely resembles techniques used in greedy optimization combined with counting patterns inside a string. The counting process is essentially a running accumulation similar to a prefix sum over character frequencies.
Recommended for interviews: The greedy enumeration approach with prefix counting is what interviewers expect. The brute force method demonstrates understanding of subsequence counting, but the O(n) solution shows you can reason about how insertion affects pair formation and avoid unnecessary recomputation.
Solution
We can first calculate the number of "LCT" subsequences in the original string, then consider the case of inserting one letter.
The number of "LCT" subsequences can be calculated by traversing the string. We can enumerate the middle "C" and use two variables l and r to maintain the counts of "L" on the left and "T" on the right respectively. For each "C", we can calculate the number of "L"s on its left and the number of "T"s on its right, thus obtaining the number of "LCT" subsequences with this "C" as the middle character as l times r, and accumulate it to the total count.
Next, we need to consider the case of inserting one letter. Consider inserting an "L", "C", or "T":
- Insert an "L": we only need to count the number of "CT" subsequences in the original string.
- Insert a "T": we only need to count the number of "LC" subsequences in the original string.
- Insert a "C": we only need to count the number of "LT" subsequences in the original string. In this case, during the enumeration process above, we can maintain a variable
mxrepresenting the current maximum value ofl times r.
Finally, we add the number of "LCT" subsequences in the original string to the maximum number of subsequences after inserting one letter to get the final result.
The time complexity is O(n), where n is the length of the string. The space complexity is O(1).
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 ansclass Solution {
private char[] s;
public long numOfSubsequences(String S) {
s = S.toCharArray();
int l = 0, r = 0;
for (char c : s) {
if (c == 'T') {
++r;
}
}
long ans = 0, mx = 0;
for (char c : s) {
r -= c == 'T' ? 1 : 0;
if (c == 'C') {
ans += 1L * l * r;
}
l += c == 'L' ? 1 : 0;
mx = Math.max(mx, 1L * l * r);
}
mx = Math.max(mx, Math.max(calc("LC"), calc("CT")));
ans += mx;
return ans;
}
private long calc(String t) {
long cnt = 0;
int a = 0;
for (char c : s) {
if (c == t.charAt(1)) {
cnt += a;
}
a += c == t.charAt(0) ? 1 : 0;
}
return cnt;
}
}class Solution {
public:
long long numOfSubsequences(string s) {
auto calc = [&](string t) {
long long cnt = 0, a = 0;
for (char c : s) {
if (c == t[1]) {
cnt += a;
}
a += (c == t[0]);
}
return cnt;
};
long long l = 0, r = count(s.begin(), s.end(), 'T');
long long ans = 0, mx = 0;
for (char c : s) {
r -= (c == 'T');
if (c == 'C') {
ans += l * r;
}
l += (c == 'L');
mx = max(mx, l * r);
}
mx = max(mx, calc("LC"));
mx = max(mx, calc("CT"));
ans += mx;
return ans;
}
};function numOfSubsequences(s: string): number {
const calc = (t: string): number => {
let [cnt, a] = [0, 0];
for (const c of s) {
if (c === t[1]) cnt += a;
if (c === t[0]) a++;
}
return cnt;
};
let [l, r] = [0, 0];
for (const c of s) {
if (c === 'T') r++;
}
let [ans, mx] = [0, 0];
for (const c of s) {
if (c === 'T') r--;
if (c === 'C') ans += l * r;
if (c === 'L') l++;
mx = Math.max(mx, l * r);
}
mx = Math.max(mx, calc('LC'));
mx = Math.max(mx, calc('CT'));
ans += mx;
return ans;
}func numOfSubsequences(s string) int64 {
calc := func(t string) int64 {
cnt, a := int64(0), int64(0)
for _, c := range s {
if c == rune(t[1]) {
cnt += a
}
if c == rune(t[0]) {
a++
}
}
return cnt
}
l, r := int64(0), int64(0)
for _, c := range s {
if c == 'T' {
r++
}
}
ans, mx := int64(0), int64(0)
for _, c := range s {
if c == 'T' {
r--
}
if c == 'C' {
ans += l * r
}
if c == 'L' {
l++
}
mx = max(mx, l*r)
}
mx = max(mx, calc("LC"), calc("CT"))
ans += mx
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Insertion Enumeration | O(n²) | O(1) | Useful for understanding subsequence counting or when constraints are very small |
| Greedy Enumeration with Prefix Counting | O(n) | O(1) | Best general solution. Efficient for large strings and commonly expected in interviews |
Frequently asked questions
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.