3948. Maximum Number Of Subsequences After One Inserting¶
3948. Maximum Number of Subsequences After One Inserting
Medium
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.
A subsequence is a non-empty string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.
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.
Solution¶
class Solution {
public long numOfSubsequences(String s) {
int n = s.length();
long pref[] = new long[n + 1];
long suff[] = new long[n + 1];
for (int i = 0; i < n; i++) {
pref[i + 1] = pref[i] + (s.charAt(i) == 'L' ? 1 : 0);
}
for (int i = n - 1; i >= 0; i--) {
suff[i] += suff[i + 1] + (s.charAt(i) == 'T' ? 1 : 0);
}
long l = 0, c = 0, t = 0, placeC = 0;
for (int i = 0; i < n; i++) {
char current = s.charAt(i);
if (current == 'C') {
c += (pref[i] * suff[i + 1]);
l += ((pref[i] + 1) * (suff[i + 1]));
t += (pref[i] * (suff[i + 1] + 1));
}
else
placeC = Math.max(placeC, pref[i] * suff[i]);
}
c += placeC;
return Math.max(Math.max(l, c), t);
}
}
Complexity Analysis¶
- Time Complexity: O(?)
- Space Complexity: O(?)
Explanation¶
[Add detailed explanation here]