Medium

题目描述

给定一个由大写英文字母组成的字符串 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 <= 10^5
  • s 由大写英文字母组成

解题思路

这道题要求在插入一个字符后最大化 “LCT” 子序列的数量。我们需要理解 “LCT” 子序列的形成规律：对于每个位置 i，如果 s[i] = 'C'，那么它左边的 ‘L’ 数量与右边的 ‘T’ 数量的乘积就是以该 ‘C’ 为中心的 “LCT” 子序列数量。

解题思路：

  1. 预处理数组：

    • preL[i]：位置 i 左边（包含 i）的 ‘L’ 数量
    • preLC[i]：位置 i 左边（包含 i）的 “LC” 子序列数量
    • sufT[i]：位置 i 右边（包含 i）的 ‘T’ 数量
    • sufCT[i]：位置 i 右边（包含 i）的 “CT” 子序列数量

  2. 计算基础值：不插入任何字符时的 “LCT” 子序列数量 base = Σ(preLC[i] * sufT[i])，其中 s[i] = 'T'

  3. 枚举插入位置：对于每个可能的插入位置 i（包括字符串开头和结尾），计算插入不同字符的收益：

    • 插入 ‘L’：增加 sufCT[i] 个子序列
    • 插入 ‘C’：增加 preL[i] * sufT[i] 个子序列
    • 插入 ‘T’：增加 preLC[i] 个子序列

  4. 选择最优方案：取所有可能的插入方案中收益最大的那个

这种方法的关键在于通过预处理避免重复计算，时间复杂度为 O(n)。

代码实现

class Solution {
public:
    long long numOfSubsequences(string s) {
        int n = s.length();
        
        // 预处理数组
        vector<long long> preL(n + 1, 0), preLC(n + 1, 0);
        vector<long long> sufT(n + 1, 0), sufCT(n + 1, 0);
        
        // 计算前缀数组
        for (int i = 0; i < n; i++) {
            preL[i + 1] = preL[i] + (s[i] == 'L' ? 1 : 0);
            preLC[i + 1] = preLC[i] + (s[i] == 'C' ? preL[i + 1] : 0);
        }
        
        // 计算后缀数组
        for (int i = n - 1; i >= 0; i--) {
            sufT[i] = sufT[i + 1] + (s[i] == 'T' ? 1 : 0);
            sufCT[i] = sufCT[i + 1] + (s[i] == 'C' ? sufT[i + 1] : 0);
        }
        
        // 计算基础值
        long long base = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'T') {
                base += preLC[i];
            }
        }
        
        long long maxVal = base;
        
        // 枚举插入位置
        for (int i = 0; i <= n; i++) {
            // 插入 'L'
            long long gainL = sufCT[i];
            maxVal = max(maxVal, base + gainL);
            
            // 插入 'C'
            long long gainC = preL[i] * sufT[i];
            maxVal = max(maxVal, base + gainC);
            
            // 插入 'T'
            long long gainT = preLC[i];
            maxVal = max(maxVal, base + gainT);
        }
        
        return maxVal;
    }
};

class Solution:
    def numOfSubsequences(self, s: str) -> int:
        n = len(s)
        
        # 预处理数组
        preL = [0] * (n + 1)
        preLC = [0] * (n + 1)
        sufT = [0] * (n + 1)
        sufCT = [0] * (n + 1)
        
        # 计算前缀数组
        for i in range(n):
            preL[i + 1] = preL[i] + (1 if s[i] == 'L' else 0)
            preLC[i + 1] = preLC[i] + (preL[i + 1] if s[i] == 'C' else 0)
        
        # 计算后缀数组
        for i in range(n - 1, -1, -1):
            sufT[i] = sufT[i + 1] + (1 if s[i] == 'T' else 0)
            sufCT[i] = sufCT[i + 1] + (sufT[i + 1] if s[i] == 'C' else 0)
        
        # 计算基础值
        base = 0
        for i in range(n):
            if s[i] == 'T':
                base += preLC[i]
        
        max_val = base
        
        # 枚举插入位置
        for i in range(n + 1):
            # 插入 'L'
            gain_L = sufCT[i]
            max_val = max(max_val, base + gain_L)
            
            # 插入 'C'
            gain_C = preL[i] * sufT[i]
            max_val = max(max_val, base + gain_C)
            
            # 插入 'T'
            gain_T = preLC[i]
            max_val = max(max_val, base + gain_T)
        
        return max_val

public class Solution {
    public long NumOfSubsequences(string s) {
        int n = s.Length;
        
        // 预处理数组
        long[] preL = new long[n + 1];
        long[] preLC = new long[n + 1];
        long[] sufT = new long[n + 1];
        long[] sufCT = new long[n + 1];
        
        // 计算前缀数组
        for (int i = 0; i < n; i++) {
            preL[i + 1] = preL[i] + (s[i] == 'L' ? 1 : 0);
            preLC[i + 1] = preLC[i] + (s[i] == 'C' ? preL[i + 1] : 0);
        }
        
        // 计算后缀数组
        for (int i = n - 1; i >= 0; i--) {
            sufT[i] = sufT[i + 1] + (s[i] == 'T' ? 1 : 0);
            sufCT[i] = sufCT[i + 1] + (s[i] == 'C' ? sufT[i + 1] : 0);
        }
        
        // 计算基础值
        long baseVal = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'T') {
                baseVal += preLC[i];
            }
        }
        
        long maxVal = baseVal;
        
        // 枚举插入位置
        for (int i = 0; i <= n; i++) {
            // 插入 'L'
            long gainL = sufCT[i];
            maxVal = Math.Max(maxVal, baseVal + gainL);
            
            // 插入 'C'
            long gainC = preL[i] * sufT[i];
            maxVal = Math.Max(maxVal, baseVal + gainC);
            
            // 插入 'T'
            long gainT = preLC[i];
            maxVal = Math.Max(maxVal, baseVal + gainT);
        }
        
        return maxVal;
    }
}

var numOfSubsequences = function(s) {
    const n = s.length;
    
    // 预处理数组
    const preL = new Array(n + 1).fill(0);
    const preLC = new Array(n + 1).fill(0);
    const sufT = new Array(n + 1).fill(0);
    const sufCT = new Array(n + 1).fill(0);
    
    // 计算前缀数组
    for (let i = 0; i < n; i++) {
        preL[i + 1] = preL[i] + (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串 s 的长度。我们需要遍历字符串三次：一次计算前缀数组，一次计算后缀数组，一次枚举插入位置。空间复杂度主要来自四个预处理数组的存储。