Solution: Maximum Score From Removing Substrings (ver. 2)

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Note: This is my second version of a solution post for this problem. This one is the better solution, but the first version used a cool concept.

---

Leetcode Problem #1717 (Medium): 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.

---

Examples:

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.

---

Idea:

Note: This is my second solution post for this problem. I still consider the other solution to be a cool approach, but this one is definitely more efficient and easier to follow.

One of the easy things to realize about this problem is that we can break the string up into chunks; Only contiguous sets of "a" and "b" will be meaningful, and any time we see a character other than those two, we effectively end one segment and wait to begin another.

The other thing we can realize fairly easily is that we should greedily prioritize whichever pattern is worth more. To make things easier, we can prefix our main code with some variable swaps depending on which pattern has a higher value. For the remainder of this post, we can just assume that "ab" > "ba" and therefore a = "a" and b = "b".

If we consider a segment of mixed "a"'s and "b"'s, we should have little problem going through it and accounting for all matches to the better pattern. We'll just need to keep track of how many a's are immeditely behind our current progress in order to match up with later b's.

But how do we deal with matching the Y pattern after matching the X pattern as much as possible? To answer that, we have to think about what such a modified string would look like:

segment = "bbaababbaa"                       // initial segment
segment = "bbaa"                             // after pulling out all "ab" patterns

segment = "bbbbabababaaabababaaaabababaaa"   // initial segment
segment = "bbbbaaaaaaaa"                     // after pulling out all "ab" patterns

You can see that after matching all possible "ab" patterns, we will always be left with a similar looking remaining segment: a number of b's followed by a number of a's. From here, we can obviously make as many "ba" matches as there are of the smallest number between the counts of a and b.

Then we just need to remember to clear the store once we reach the end of each segment.

---

Implementation:

Unlike the other languages, Java has no convenient way to swap variable contents.

We should either run the iteration one past the end of S, or else add the final Y matches to our return value just in case the last segment goes up to the end of S.

---

Javascript Code:

var maximumGain = function(S, X, Y) {
    let len = S.length, ans = 0, a = "a", b = "b"
    if (Y > X) [a,b,X,Y] = [b,a,Y,X]
    let aStore = 0, bStore = 0
    for (let i = 0, c = S[i]; i <= len; c = S[++i])
        if (c === a) aStore++
        else if (c === b)
            if (aStore) ans += X, aStore--
            else bStore++
        else ans += Y * Math.min(aStore, bStore), aStore = bStore = 0
    return ans
};

---

Python Code:

class Solution:
    def maximumGain(self, S: str, X: int, Y: int) -> int:
        a,b, ans, aStore,bStore = "a","b", 0, 0,0
        if Y > X: a,b,X,Y = b,a,Y,X
        for c in S:
            if c == a: aStore += 1
            elif c == b:
                if aStore:
                    ans += X
                    aStore -= 1
                else: bStore += 1
            else:
                ans += Y * min(aStore, bStore)
                aStore,bStore = 0,0
        return ans + Y * min(aStore, bStore)

---

Java Code:

class Solution {
    public int maximumGain(String S, int X, int Y) {
        char a = 'a', b = 'b';
        int ans = 0, aStore = 0, bStore = 0;
        if (Y > X) {
            char ctemp = a;
            a = b;
            b = ctemp;
            int itemp = X;
            X = Y;
            Y = itemp;
        }
        for (char c: S.toCharArray())
            if (c == a) aStore++;
            else if (c == b)
                if (aStore > 0) {
                    ans += X;
                    aStore--;
                } else bStore++;
            else {
                ans += Y * Math.min(aStore, bStore);
                aStore = bStore = 0;
            }
        return ans + Y * Math.min(aStore, bStore);
    }
}

---

C++ Code:

class Solution {
public:
    int maximumGain(string S, int X, int Y) {
        char a = 'a', b = 'b';
        int ans = 0, aStore = 0, bStore = 0;
        if (Y > X) swap(a,b), swap(X,Y);
        for (char c: S)
            if (c == a) aStore++;
            else if (c == b)
                if (aStore > 0) ans += X, aStore--;
                else bStore++;
            else ans += Y * min(aStore, bStore), aStore = bStore = 0;
        return ans + Y * min(aStore, bStore);
    }
};