LeetCode 3628 - Maximum Number of Subsequences After One Inserting
We are given a string consisting of uppercase English letters. From this string, we are interested in counting subsequences equal to the pattern "LCT", where a subsequence means indices such that , , and .
Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Greedy, Prefix Sum
Solution
Problem Understanding
We are given a string $s$ consisting of uppercase English letters. From this string, we are interested in counting subsequences equal to the pattern "LCT", where a subsequence means indices $i < j < k$ such that $s[i] = \text{L}$, $s[j] = \text{C}$, and $s[k] = \text{T}$.
We are allowed to insert at most one uppercase English letter at any position in the string, including the beginning or the end. After performing this optional insertion, we count how many subsequences equal to "LCT" exist in the resulting string, and we must maximize this number.
The input is a single string $s$, with length up to $10^5$. The output is a single integer, the maximum possible number of "LCT" subsequences achievable after at most one insertion.
The constraint on length immediately rules out any cubic or even quadratic enumeration of subsequences or insertion positions. The solution must be linear or near-linear.
Important edge cases include strings with fewer than three relevant characters, strings with no valid "LCT" formation, and cases where insertion is essential to create any valid subsequence at all.
Approaches
Brute Force Approach
A direct method is to try inserting each possible letter from 'A' to 'Z' at every possible position in the string. For each resulting string, we compute the number of "LCT" subsequences using a triple nested scan or dynamic counting.
This approach is correct because it explicitly explores all valid transformations of the string under the allowed operation. However, it is computationally infeasible. There are $O(26n)$ insertions, and each evaluation of subsequences takes $O(n)$, yielding $O(26n^2)$, which is far beyond acceptable limits for $n = 10^5$.
Key Insight
We observe that only inserting letters 'L', 'C', or 'T' can ever improve the count. Any other letter does not participate in forming "LCT" subsequences and is strictly suboptimal.
Thus, we reduce the problem to evaluating three cases:
Inserting 'L' improves subsequences by allowing this new 'L' to pair with existing "CT" subsequences to its right.
Inserting 'T' improves subsequences by allowing existing "LC" subsequences to the left to pair with this new 'T'.
Inserting 'C' improves subsequences by splitting the string into left and right parts, where each 'L' on the left and 'T' on the right contribute multiplicatively.
This transforms the problem into prefix-suffix aggregation over counts of 'L', 'C', and 'T', along with derived subsequence counts "LC", "CT", and "LCT".
Complexity Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | $O(n^2)$ | $O(n)$ | Try all insertions and recompute subsequences |
| Optimal | $O(n)$ | $O(n)$ | Prefix-suffix DP for L, C, T interactions |
Algorithm Walkthrough
We construct the solution by decomposing the effect of insertion into three independent candidates.
First, we compute the number of "LCT" subsequences in the original string using a standard linear scan. We maintain three accumulators: the number of 'L' seen so far, the number of "LC" subsequences formed so far, and the number of "LCT" subsequences formed so far. Each 'C' extends existing 'L', and each 'T' extends existing "LC".
Second, we precompute prefix information. Let prefix_L[i] be the number of 'L' in $s[0:i)$, and prefix_LC[i] be the number of "LC" subsequences in the prefix.
Third, we precompute suffix information symmetrically. Let suffix_T[i] be the number of 'T' in $s[i:n)$, and suffix_CT[i] be the number of "CT" subsequences in the suffix.
Now we evaluate insertion cases.
For inserting 'L' at position $i$, the gain is exactly the number of "CT" subsequences in the suffix starting at $i$, since the inserted 'L' can pair with any existing "CT" subsequence to its right.
For inserting 'T' at position $i$, the gain is exactly the number of "LC" subsequences in the prefix ending at $i$, since any "LC" to the left can extend to the inserted 'T'.
For inserting 'C' at position $i$, every 'L' to the left and every 'T' to the right combine through the inserted 'C', yielding a gain of:
$$(#L \text{ in prefix}) \times (#T \text{ in suffix})$$
Finally, we take the maximum over all insertion positions and all three letter choices.
Why it works
The crucial invariant is that every valid "LCT" subsequence either exists entirely in the original string or uses the newly inserted character exactly once. By classifying subsequences based on whether they use the inserted character and its role (L, C, or T), we exhaust all structural possibilities without overlap or omission. Linearity follows from the fact that all contributions reduce to prefix and suffix aggregates.
Python Solution
class Solution:
def numOfSubsequences(self, s: str) -> int:
n = len(s)
# Base LCT count
l_count = 0
lc_count = 0
lct_count = 0
for ch in s:
if ch == 'L':
l_count += 1
elif ch == 'C':
lc_count += l_count
elif ch == 'T':
lct_count += lc_count
# Prefix L and LC
prefix_L = [0] * (n + 1)
prefix_LC = [0] * (n + 1)
l = 0
lc = 0
for i in range(n):
prefix_L[i + 1] = prefix_L[i]
prefix_LC[i + 1] = prefix_LC[i]
if s[i] == 'L':
l += 1
prefix_L[i + 1] = l
elif s[i] == 'C':
lc += l
prefix_LC[i + 1] = lc
# Suffix T and CT
suffix_T = [0] * (n + 1)
suffix_CT = [0] * (n + 1)
t = 0
ct = 0
for i in range(n - 1, -1, -1):
suffix_T[i] = suffix_T[i + 1]
suffix_CT[i] = suffix_CT[i + 1]
if s[i] == 'T':
t += 1
suffix_T[i] = t
elif s[i] == 'C':
ct += t
suffix_CT[i] = ct
best = lct_count
for i in range(n + 1):
best = max(best, lct_count + suffix_CT[i]) # insert L
best = max(best, lct_count + prefix_LC[i]) # insert T
best = max(best, lct_count + prefix_L[i] * suffix_T[i]) # insert C
return best
Implementation Notes
The code separates the computation into independent prefix and suffix passes, each maintaining linear state machines for subsequence counting. The final loop evaluates all insertion points in constant time per position, ensuring global optimality.
The design mirrors a decomposition of a combinatorial structure into independent directional accumulations.
Go Solution
func numOfSubsequences(s string) int64 {
n := len(s)
var lCount, lcCount, lctCount int64
for i := 0; i < n; i++ {
switch s[i] {
case 'L':
lCount++
case 'C':
lcCount += lCount
case 'T':
lctCount += lcCount
}
}
prefixL := make([]int64, n+1)
prefixLC := make([]int64, n+1)
var l, lc int64
for i := 0; i < n; i++ {
prefixL[i+1] = prefixL[i]
prefixLC[i+1] = prefixLC[i]
if s[i] == 'L' {
l++
prefixL[i+1] = l
} else if s[i] == 'C' {
lc += l
prefixLC[i+1] = lc
}
}
suffixT := make([]int64, n+1)
suffixCT := make([]int64, n+1)
var t, ct int64
for i := n - 1; i >= 0; i-- {
suffixT[i] = suffixT[i+1]
suffixCT[i] = suffixCT[i+1]
if s[i] == 'T' {
t++
suffixT[i] = t
} else if s[i] == 'C' {
ct += t
suffixCT[i] = ct
}
}
best := lctCount
for i := 0; i <= n; i++ {
gainL := suffixCT[i]
gainT := prefixLC[i]
gainC := prefixL[i] * suffixT[i]
if lctCount+gainL > best {
best = lctCount + gainL
}
if lctCount+gainT > best {
best = lctCount + gainT
}
if lctCount+gainC > best {
best = lctCount + gainC
}
}
return best
}
Go-specific Notes
The Go implementation uses explicit int64 to avoid overflow, since subsequence counts can grow quadratically in the worst case. Slices are used for prefix and suffix arrays, matching the dynamic nature of the string indexing. The logic mirrors the Python version exactly, with careful separation of accumulation states.
Worked Examples
Example 1: s = "LMCT"
Base computation yields one "LCT" subsequence from indices (0,2,3). We evaluate insertion positions.
At position 0, inserting 'L' increases suffix "CT" count by 1, yielding total 2.
At other positions, no better improvement occurs.
Thus the maximum is 2.
Example 2: s = "LCCT"
Base "LCT" count is 2. Prefix and suffix structure shows that inserting 'L' at position 0 increases available "CT" subsequences from 2 to 4 total combinations.
The algorithm identifies suffix "CT" count as 2 at position 0, so gain is 2, yielding 4 total.
Example 3: s = "L"
No "CT" or "LC" structure exists. All gains from insertion fail to complete a valid triple. Prefix and suffix arrays are zero everywhere, so result remains 0.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | $O(n)$ | Three linear passes plus one linear evaluation of insertion points |
| Space | $O(n)$ | Prefix and suffix arrays store aggregated counts |
The algorithm is linear because each character contributes a constant number of updates in each pass, and no nested iteration over the string is performed.
Test Cases
assert Solution().numOfSubsequences("LMCT") == 2 # basic insertion improves L-start
assert Solution().numOfSubsequences("LCCT") == 4 # multiple CT pairs amplified by insertion
assert Solution().numOfSubsequences("L") == 0 # impossible to form LCT
assert Solution().numOfSubsequences("LCT") == 2 # inserting L or T improves count
assert Solution().numOfSubsequences("LLCCCTTT") > 0 # dense structure stress test
assert Solution().numOfSubsequences("AAAAA") == 0 # irrelevant letters only
| Test | Why |
|---|---|
"LMCT" |
validates insertion increasing CT contribution |
"LCCT" |
validates multiplicative structure of C insertion effect |
"L" |
minimal length, impossible base formation |
"LCT" |
checks whether insertion can improve already valid base |
"LLCCCTTT" |
stress test for combinatorial growth |
"AAAAA" |
ensures irrelevant letters do not affect result |
Edge Cases
One important edge case occurs when the string contains no 'L' or no 'T'. In such cases, only insertion of specific letters can create a valid subsequence, and the algorithm correctly yields zero unless a full structure can be formed through insertion.
Another edge case is when the string is already very small, particularly length one or two. Here, all prefix and suffix structures collapse to zero arrays, and the algorithm avoids invalid indexing by using extended arrays of size $n+1$.
A final subtle case arises when all characters are identical. Although prefix and suffix counts may grow for individual letters, no valid "LCT" structure can emerge, and all computed gains remain zero, ensuring correctness.