Maximize number of subsequences in a string

String Greedy Prefix Sum

36.0% acceptance

Feb 25, 2026

530

You are given a 0-indexed string text and another 0-indexed string pattern of length 2, both of which consist of only lowercase English letters. You can add either pattern[0] or pattern[1] anywhere in text exactly once. Note that the character can be added even at the beginning or at the end of text. Return the maximum number of times pattern can occur as a subsequence of the modified text. A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_subsequence_count(text: String, pattern: String) -> i64 {
    let p: Vec<char> = pattern.chars().collect();
    let (p0, p1) = (p[0], p[1]);
    let mut count_p0: i64 = 0;
    let mut count_p1: i64 = 0;
    let mut current: i64 = 0;
    for c in text.chars() {
      if c == p1 {
        current += count_p0;
        count_p1 += 1;
      }
      if c == p0 {
        count_p0 += 1;
      }
    }
    // Add p0 at start: every p1 in text is now paired with this p0 + existing
    // Add p1 at end: every p0 in text gets an extra p1
    current + count_p0.max(count_p1)
  }
}