Formatted question description: https://leetcode.ca/all/1717.html

1717. Maximum Score From Removing Substrings

Level

Medium

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 <= 10^5
• 1 <= x, y <= 10^4
• s consists of lowercase English letters.

Solution

Use a greedy approach. If x >= y, then consider removing "ab" first and removing "ba" next. Otherwise, consider removing "ba" first and removing "ab" next.

When removing substrings, update the score and generate the new string after removing the substrings, so that the next steps can be proceeded as well.

Finally, return the score.

class Solution {
    int points = 0;

    public int maximumGain(String s, int x, int y) {
        if (x >= y) {
            s = remove1(s, x);
            s = remove2(s, y);
        } else {
            s = remove2(s, y);
            s = remove1(s, x);
        }
        return points;
    }

    public String remove1(String s, int x) {
        StringBuffer sb = new StringBuffer();
        int length = s.length();
        int index = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (index > 0 && c == 'b' && sb.charAt(index - 1) == 'a') {
                points += x;
                sb.deleteCharAt(index - 1);
                index--;
            } else {
                sb.append(c);
                index++;
            }
        }
        return sb.toString();
    }

    public String remove2(String s, int y) {
        StringBuffer sb = new StringBuffer();
        int length = s.length();
        int index = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (index > 0 && c == 'a' && sb.charAt(index - 1) == 'b') {
                points += y;
                sb.deleteCharAt(index - 1);
                index--;
            } else {
                sb.append(c);
                index++;
            }
        }
        return sb.toString();
    }
}

All Problems

All Solutions