Maximum number of subsequences after one inserting

String Dynamic Programming Greedy Prefix Sum

31.7% acceptance

Feb 25, 2026

130

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn num_of_subsequences(s: String) -> i64 {
    let chars: Vec<char> = s.chars().collect();
    let n = chars.len();

    // Count current "LCT" subsequences
    // l[i] = # L's in chars[0..=i]
    // lc[i] = # LC subsequences in chars[0..=i]
    // lct = total LCT subsequences
    let count_lct = |s: &[char]| -> i64 {
      let mut l = 0i64;
      let mut lc = 0i64;
      let mut lct = 0i64;
      for &c in s {
        match c {
          'L' => l += 1,
          'C' => lc += l,
          'T' => lct += lc,
          _ => {}
        }
      }
      lct
    };

    let base = count_lct(&chars);

    // Try inserting each of L, C, T at each position i (before chars[i]).
    //
    // Insert 'L' at i: gain = # "CT" subsequences in chars[i..]
    //   = suffix_ct[i]
    //
    // Insert 'C' at i: gain = (# L's before i) * (# T's from i onwards)
    //   = prefix_l[i] * suffix_t[i]
    //
    // Insert 'T' at i: gain = # "LC" subsequences in chars[0..i)
    //   = prefix_lc[i]

    // prefix_l[i]  = # L's in chars[0..i)  (exclusive)
    // prefix_lc[i] = # LC subsequences in chars[0..i)  (exclusive)
    let mut prefix_l = vec![0i64; n + 1];
    let mut prefix_lc = vec![0i64; n + 1];
    let mut l = 0i64;
    let mut lc = 0i64;
    for i in 0..n {
      prefix_l[i] = l;
      prefix_lc[i] = lc;
      match chars[i] {
        'L' => l += 1,
        'C' => lc += l,
        _ => {}
      }
    }
    prefix_l[n] = l;
    prefix_lc[n] = lc;

    // suffix_t[i]  = # T's in chars[i..]  (inclusive)
    // suffix_ct[i] = # "CT" subsequences in chars[i..]  (inclusive)
    let mut suffix_t = vec![0i64; n + 1];
    let mut suffix_ct = vec![0i64; n + 1];
    for i in (0..n).rev() {
      suffix_t[i] = suffix_t[i + 1] + if chars[i] == 'T' { 1 } else { 0 };
      suffix_ct[i] = suffix_ct[i + 1] + if chars[i] == 'C' { suffix_t[i + 1] } else { 0 };
    }

    let mut max_gain = 0i64;
    for i in 0..=n {
      // Insert L at position i: gain = # CT subsequences in chars[i..]
      let gain_l = suffix_ct[i.min(n)];
      // Insert C at position i: gain = L's before i * T's from i onwards
      let gain_c = prefix_l[i] * suffix_t[i.min(n)];
      // Insert T at position i: gain = LC subsequences before i
      let gain_t = prefix_lc[i];
      max_gain = max_gain.max(gain_l).max(gain_c).max(gain_t);
    }

    base + max_gain
  }
}