Question

1717. Maximum Score From Removing Substrings

中文文档

Description

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.
  • For example, when removing "ab" from "cabxbae" it becomes "cxbae".
• Remove substring "ba" and gain y points.
  • For example, when removing "ba" from "cabxbae" it becomes "cabxe".

Return _the maximum points you can gain after applying the above operations on_ s.

 

Example 1:

Input: s = "cdbcbbaaabab", x = 4, y = 5
Output: 19
Explanation:
- Remove the "ba" underlined in "cdbcbbaaabab". Now, s = "cdbcbbaaab" and 5 points are added to the score.
- Remove the "ab" underlined in "cdbcbbaaab". Now, s = "cdbcbbaa" and 4 points are added to the score.
- Remove the "ba" underlined in "cdbcbbaa". Now, s = "cdbcba" and 5 points are added to the score.
- Remove the "ba" underlined in "cdbcba". Now, s = "cdbc" and 5 points are added to the score.
Total score = 5 + 4 + 5 + 5 = 19.

Example 2:

Input: s = "aabbaaxybbaabb", x = 5, y = 4
Output: 20

 

Constraints:

• 1 <= s.length <= 105
• 1 <= x, y <= 104
• s consists of lowercase English letters.

Solutions

Solution 1

class Solution:
  def maximumGain(self, s: str, x: int, y: int) -> int:
    if x < y:
      return self.maximumGain(s[::-1], y, x)
    ans = 0
    stk1, stk2 = [], []
    for c in s:
      if c != 'b':
        stk1.append(c)
      else:
        if stk1 and stk1[-1] == 'a':
          stk1.pop()
          ans += x
        else:
          stk1.append(c)
    while stk1:
      c = stk1.pop()
      if c != 'b':
        stk2.append(c)
      else:
        if stk2 and stk2[-1] == 'a':
          stk2.pop()
          ans += y
        else:
          stk2.append(c)
    return ans

class Solution {
  public int maximumGain(String s, int x, int y) {
    if (x < y) {
      return maximumGain(new StringBuilder(s).reverse().toString(), y, x);
    }
    int ans = 0;
    Deque<Character> stk1 = new ArrayDeque<>();
    Deque<Character> stk2 = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
      if (c != 'b') {
        stk1.push(c);
      } else {
        if (!stk1.isEmpty() && stk1.peek() == 'a') {
          stk1.pop();
          ans += x;
        } else {
          stk1.push(c);
        }
      }
    }
    while (!stk1.isEmpty()) {
      char c = stk1.pop();
      if (c != 'b') {
        stk2.push(c);
      } else {
        if (!stk2.isEmpty() && stk2.peek() == 'a') {
          stk2.pop();
          ans += y;
        } else {
          stk2.push(c);
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maximumGain(string s, int x, int y) {
    if (x < y) {
      reverse(s.begin(), s.end());
      return maximumGain(s, y, x);
    }
    int ans = 0;
    stack<char> stk1;
    stack<char> stk2;
    for (char c : s) {
      if (c != 'b')
        stk1.push(c);
      else {
        if (!stk1.empty() && stk1.top() == 'a') {
          stk1.pop();
          ans += x;
        } else
          stk1.push(c);
      }
    }
    while (!stk1.empty()) {
      char c = stk1.top();
      stk1.pop();
      if (c != 'b')
        stk2.push(c);
      else {
        if (!stk2.empty() && stk2.top() == 'a') {
          stk2.pop();
          ans += y;
        } else
          stk2.push(c);
      }
    }
    return ans;
  }
};

func maximumGain(s string, x int, y int) int {
  if x < y {
    t := []rune(s)
    for i, j := 0, len(t)-1; i < j; i, j = i+1, j-1 {
      t[i], t[j] = t[j], t[i]
    }
    return maximumGain(string(t), y, x)
  }
  ans := 0
  var stk1 []byte
  var stk2 []byte
  for i := range s {
    if s[i] != 'b' {
      stk1 = append(stk1, s[i])
    } else {
      if len(stk1) > 0 && stk1[len(stk1)-1] == 'a' {
        stk1 = stk1[0 : len(stk1)-1]
        ans += x
      } else {
        stk1 = append(stk1, s[i])
      }
    }
  }
  for _, c := range stk1 {
    if c != 'a' {
      stk2 = append(stk2, c)
    } else {
      if len(stk2) > 0 && stk2[len(stk2)-1] == 'b' {
        stk2 = stk2[0 : len(stk2)-1]
        ans += y
      } else {
        stk2 = append(stk2, c)
      }
    }
  }
  return ans
}