题目描述
给你一个由大写英文字母组成的字符串 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 <= 105s 仅由大写英文字母组成。
解法
方法一：枚举
我们可以先计算出原字符串中 "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 | 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
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 | class 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;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | 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;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38 | 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
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | 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;
}
|