Maximum score from removing substrings

String Stack Greedy

66.6% acceptance

Feb 25, 2026

1920

137

You are given a string s and two integers x and y. You can perform two types of operations any number of times. Remove substring "ab" and gain x points. Remove substring "ba" and gain y points. Return the maximum points you can gain after applying the above operations on s.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_gain(s: String, x: i32, y: i32) -> i32 {
    // Always remove the higher-value pair first
    let (first, second, fx, sy) = if x >= y {
      (b'a', b'b', x, y)  // "ab" first
    } else {
      (b'b', b'a', y, x)  // "ba" first
    };
    let mut score = 0;
    let mut stack1: Vec<u8> = Vec::new();
    for &c in s.as_bytes() {
      if c == second && stack1.last() == Some(&first) {
        stack1.pop();
        score += fx;
      } else {
        stack1.push(c);
      }
    }
    let mut stack2: Vec<u8> = Vec::new();
    for &c in &stack1 {
      if c == first && stack2.last() == Some(&second) {
        stack2.pop();
        score += sy;
      } else {
        stack2.push(c);
      }
    }
    score
  }
}