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 = (type, pointX, pointY) => {
    const [firstChar, secondChar] = type;
    let result = (firstCount = secondCount = 0);

    for (const char of s) {
      if (char === firstChar) firstCount += 1;
      else if (char === secondChar) {
        if (firstCount) {
          firstCount -= 1;
          result += pointX;
          continue;
        }
        secondCount += 1;
      } else {
        result += Math.min(firstCount, secondCount) * pointY;
        firstCount = secondCount = 0;
      }
    }
    return result + Math.min(firstCount, secondCount) * pointY;
  };

  return Math.max(getScore('ab', x, y), getScore('ba', y, x));
};