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: Greedy

• Time complexity: O(n)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {string} s
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
const maximumGain = function (s, x, y) {
  const getScore = (sub, subPoint, otherPoint) => {
    const [first, second] = sub;
    let firstCount = 0;
    let secondCount = 0;
    let result = 0;

    for (const char of s) {
      if (char === first) {
        firstCount += 1;
      } else if (firstCount && char === second) {
        firstCount -= 1;
        result += subPoint;
      } else if (char === second) {
        secondCount += 1;
      } else {
        result += Math.min(firstCount, secondCount) * otherPoint;
        firstCount = 0;
        secondCount = 0;
      }
    }

    return result + Math.min(firstCount, secondCount) * otherPoint;
  };

  return x > y ? getScore('ab', x, y) : getScore('ba', y, x);
};