1717

1717. Maximum Score From Removing Substrings (Medium)

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.

  <ul>
  	<li>For example, when removing <code>"ab"</code> from <code>"c<u>ab</u>xbae"</code> it becomes <code>"cxbae"</code>.</li>
  </ul>
  </li>
  <li>Remove substring <code>"ba"</code> and gain <code>y</code> points.
  <ul>
  	<li>For example, when removing <code>"ba"</code> from <code>"cabx<u>ba</u>e"</code> it becomes <code>"cabxe"</code>.</li>
  </ul>
  </li>
  

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.

Companies:
Google

Related Topics:
String, Stack, Greedy

Solution 1. Greedy

We greedily remove the pattern with greater points, then remove the other pattern.

For removing the pattern string iteratively, we can reuse the solution to 1003. Check If Word Is Valid After Substitutions (Medium)

// OJ: https://leetcode.com/problems/maximum-score-from-removing-substrings/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
    int remove(string &s, string r, int x) {
        int i = 0, ans = 0; // `i` is write pointer, `j` is read pointer. 
        for (int j = 0; j < s.size(); ++j) {
            s[i++] = s[j];
            if (i > 1 && s[i - 2] == r[0] && s[i - 1] == r[1]) i -= 2, ans += x; // We keep removing pattern string `r` when `r` shows up in the end of written part.
        }
        s.resize(i);
        return ans;
    }
public:
    int maximumGain(string s, int x, int y) {
        string a = "ab", b = "ba";
        if (x < y) swap(a, b), swap(x, y);
        return remove(s, a, x) + remove(s, b, y);
    }
};

Proof by contradiction:

Assume score(ab) > score(ba) but removing ba first is optimal.

This could only happen when the removal of a single ab prevents 2 ba removals, and score(remove ba first) > score(remove ab first) i.e. score(ba) * 2 > score(ab).

Only b(ab)a satisfies this requirement. But after removing ab we can remove one ba, so we get score(ab) + score(ba) which is greater than score(ba) * 2.

Thus removing ba first is not optimal, the assumption is wrong.

Discuss

https://leetcode.com/problems/maximum-score-from-removing-substrings/discuss/1009028/C%2B%2B-Greedy-O(N)-Time-O(1)-Space